Hội đồng thành phố JOI có \(N\) nghị viên, đánh số từ \(1\) đến \(N\). Hội đồng sắp biểu quyết \(M\) dự thảo điều lệ, đánh số từ \(1\) đến \(M\). Nếu \(A_{i,j}=1\), nghị viên \(i\) dự định bỏ phiếu tán thành dự thảo \(j\); nếu \(A_{i,j}=0\), người đó dự định bỏ phiếu phản đối.

Phiên họp diễn ra như sau:

1. Bốc thăm chọn ngẫu nhiên một trong \(N\) nghị viên làm chủ tịch.
2. Chủ tịch chỉ định một trong \(N-1\) nghị viên còn lại làm phó chủ tịch.
3. Biểu quyết các dự thảo. Chủ tịch và phó chủ tịch không bỏ phiếu; \(N-2\) nghị viên còn lại bỏ phiếu tán thành hoặc phản đối. Một dự thảo được thông qua nếu nhận được quá nửa số phiếu của những người bỏ phiếu, tức ít nhất \(\lfloor N/2\rfloor\) phiếu tán thành. Ký hiệu \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Thị trưởng K muốn có càng nhiều điều lệ được thông qua càng tốt và đã thu thập dự định bỏ phiếu của mọi nghị viên. Với từng nghị viên, hãy tính số dự thảo được thông qua lớn nhất có thể nếu người đó được chọn làm chủ tịch, bằng cách lựa chọn phó chủ tịch phù hợp.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

N M
A_1,1 A_1,2 ... A_1,M
A_2,1 A_2,2 ... A_2,M
...
A_N,1 A_N,2 ... A_N,M

Dữ liệu ra

In \(N\) dòng ra đầu ra chuẩn. Dòng \(i\) chứa số dự thảo được thông qua lớn nhất có thể nếu nghị viên \(i\) được chọn làm chủ tịch.

Ràng buộc

• \(3\le N\le 300\,000\).
• \(1\le M\le 20\).
• \(0\le A_{i,j}\le 1\) với \(1\le i\le N\), \(1\le j\le M\).
• Mọi giá trị đầu vào đều là số nguyên.

Phân nhóm

• Nhóm 1 (8 điểm): \(N\le 300\).
• Nhóm 2 (8 điểm): \(N\le 3000\).
• Nhóm 3 (6 điểm): \(M\le 2\).
• Nhóm 4 (19 điểm): \(M\le 10\).
• Nhóm 5 (15 điểm): \(M\le 14\).
• Nhóm 6 (22 điểm): \(M\le 17\).
• Nhóm 7 (22 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 3
1 0 0
1 1 0
1 1 1

3
3
2

4 12
1 1 1 0 1 1 0 1 0 1 1 0
1 1 0 1 1 0 1 1 1 1 1 0
0 0 1 1 1 0 0 0 0 0 1 1
1 0 0 0 1 1 1 1 1 0 0 0

5
4
6
6

16 4
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

3
3
3
2
3
2
2
1
3
2
2
1
2
1
1
0

4 2
1 0
0 1
1 1
1 1

2
2
1
1

Nguồn

JOI 2022/2023 Spring Training, Contest 2, 20/03/2023. Đề gốc của JCIOI; bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.