Council

JOI시 시의회에는 1번부터 $N$번까지 번호가 매겨진 의원이 $N$명 있다. 시의회는 회의를 열고, 의원들은 1번부터 $M$번까지 번호가 매겨진 $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. 의원 중에서 제비뽑기로 의장을 무작위로 정한다.
2. 의장은 의장을 제외한 $N - 1$명의 의원 중에서 부의장을 고른다.
3. $M$개의 조례안에 대해 표결한다. 의장과 부의장을 제외한 $N - 2$명의 의원은 각 조례안에 찬성 또는 반대표를 던진다. 과반수 의원($\left\lfloor \frac{N}{2} \right\rfloor$명 이상)이 찬성한 조례안은 가결된다. 여기서 $\left\lfloor x \right\rfloor$는 $x$를 넘지 않는 가장 큰 정수이다.

JOI시 시장 K는 시의회가 최대한 많은 조례안을 가결하기를 바란다. 시장 K는 각 조례안에 대해 누가 찬성하고 누가 반대하는지 알고 있다.

의원들의 표결 정보가 주어질 때, 각 의원을 의장으로 뽑았을 때 가결될 수 있는 조례안 수의 최댓값을 구하는 프로그램을 작성하라.

표준 입력에서 다음 데이터를 읽는다.

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}

표준 출력에 $N$줄을 출력한다. $i$번째 줄에는 의원 $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$).
• 주어지는 값은 모두 정수이다.