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$。

接下来 $N$ 行，每行 $M$ 个整数 $A_{i,1},A_{i,2},\dots ,A_{i,M}$。

输出格式

输出 $N$ 行，第 $i$ 行输出一个整数，表示如果议员 $i$ 被选为议长的情况下，最多可能通过的议案数。

样例输入 1

3 3
1 0 0
1 1 0
1 1 1

样例输出 1

3
3
2

• 让我们考虑议员 $1$ 被选为议长的情况。如果议员 $2$ 被选为副议长，议会将通过 $3$ 项议案，即议案 $1,2,3$。如果议员 $3$ 被选为副议长，议会将通过 $2$ 项议案，即议案 $1,2$。因此，最大议案通过数为 $3$。第一行输出 $3$。
• 让我们考虑议员 $2$ 被选为议长的情况。如果议员 $1$ 被选为副议长，议会将通过 $3$ 项议案，即议案 $1,2,3$。如果议员 $3$ 被选为副议长，议会将通过 $1$ 项议案，即议案 $1$。因此，最大议案通过数为 $3$。第二行输出 $3$。
• 让我们考虑议员 $3$ 被选为议长的情况。如果议员 $1$ 被选为副议长，议会将通过 $2$ 项议案，即议案 $1,2$。如果议员 $2$ 被选为副议长，议会将通过 $1$ 项议案，即议案 $1$。因此，最大议案通过数为 $2$。第三行输出 $2$。

这组样例满足子任务 $1,2,4,5,6,7$ 的限制。

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

这组样例满足子任务 $1,2,5,6,7$ 的限制。

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

这组样例满足子任务 $1,2,4,5,6,7$ 的限制。

样例输入 4

4 2
1 0
0 1
1 1
1 1

样例输出 4

2
2
1
1

这组样例满足所有子任务的限制。

数据范围

对于所有输入数据，满足：

• $3\le N\le 3\times {10}^5$
• $1\le M\le 20$
• $0\le A_{i,j}\le 1(1\le i\le N,1\le j\le M)$

详细子任务附加限制及分值如下表所示。

时间限制：3s

空间限制：1024 MB