在 JOI 市的议会中，有 $N$ 名议员，编号为 $1$ 到 $N$。议会将召开会议，并对 $M$ 项提案进行投票，提案编号为 $1$ 到 $M$。如果 $A_{i,j} = 1$，则议员 $i$ ($1 \le i \le N$) 对提案 $j$ ($1 \le j \le M$) 投赞成票。如果 $A_{i,j} = 0$，则议员 $i$ 对提案 $j$ 投反对票。

JOI 市议会的运作流程如下：

1. 从 $N$ 名议员中，通过抽签随机选出一名议长。
2. 议长从除自己以外的 $N - 1$ 名议员中选出一名副议长。
3. 对 $M$ 项提案进行投票。除议长和副议长外的 $N - 2$ 名议员将对每项提案投赞成票或反对票。如果赞成票数超过或等于议员总数的半数（即大于或等于 $\lfloor \frac{N}{2} \rfloor$ 名议员投赞成票），议会即通过该提案。此处 $\lfloor x \rfloor$ 表示不超过 $x$ 的最大整数。

JOI 市市长 K 希望议会能通过尽可能多的提案。市长 K 收集了议员们的投票信息。市长 K 知道每位议员对每项提案会投赞成票还是反对票。

请编写一个程序，根据议员们的投票信息，计算出如果选定某位议员作为议长，议会所能通过的提案的最大数量。

输入格式

从标准输入读取以下数据：

$N \ M$ $A_{1,1} \ A_{1,2} \ \dots \ A_{1,M}$ $A_{2,1} \ A_{2,2} \ \dots \ A_{2,M}$ $\vdots$ $A_{N,1} \ A_{N,2} \ \dots \ A_{N,M}$

输出格式

输出 $N$ 行到标准输出。第 $i$ 行 ($1 \le i \le N$) 应包含如果选定议员 $i$ 作为议长，议会所能通过的提案的最大数量。

数据范围

• $3 \le N \le 300\,000$
• $1 \le M \le 20$
• $0 \le A_{i,j} \le 1$ ($1 \le i \le N, 1 \le j \le M$)
• 输入的所有值均为整数。

子任务

1. (8 分) $N \le 300$
2. (8 分) $N \le 3000$
3. (6 分) $M \le 2$
4. (19 分) $M \le 10$
5. (15 分) $M \le 14$
6. (22 分) $M \le 17$
7. (22 分) 无附加限制

样例

样例输入 1

3 3
1 0 0
1 1 0
1 1 1

样例输出 1

3
3
2

说明

• 考虑选定议员 1 作为议长的情况。如果选定议员 2 作为副议长，议会将通过三项提案，即提案 1、2、3。如果选定议员 3 作为副议长，议会将通过两项提案，即提案 1、2。因此，议会通过提案的最大数量为 3。第一行输出 3。
• 考虑选定议员 2 作为议长的情况。如果选定议员 1 作为副议长，议会将通过三项提案，即提案 1、2、3。如果选定议员 3 作为副议长，议会将通过一项提案，即提案 1。因此，议会通过提案的最大数量为 3。第二行输出 3。
• 考虑选定议员 3 作为议长的情况。如果选定议员 1 作为副议长，议会将通过两项提案，即提案 1、2。如果选定议员 2 作为副议长，议会将通过一项提案，即提案 1。因此，议会通过提案的最大数量为 2。第三行输出 2。

样例输入 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

样例输出 2

5
4
6
6

样例输入 3

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
3
2
3
2
2
1
3
2
2
1
2
1
1
0

样例输入 4

4 2
1 0
0 1
1 1
1 1

样例输出 4

2
2
1
1