27996번 - Council 서브태스크다국어

In the council of JOI City, there are $N$ assembly members, numbered from $1$ to $N$. The council will open a meeting, and the assembly members will take votes on $M$ proposed ordinances, numbered from $1$ to $M$. If $A_{i, j} = 1$, the assembly member $i$ ($1 ≤ i ≤ N$) will cast an affirmative vote on the proposed ordinance $j$ ($1 ≤ j ≤ M$). If $A_{i, j} = 0$, the assembly member $i$ will cast a negative vote on the proposed ordinance $j$.

The council of JOI City will be performed as follows.

1. Among the $N$ assembly members, they will randomly choose a chairperson by drawing lots.
2. The chairperson will choose a deputy chairperson among the $N - 1$ assembly members except for the chairperson.
3. The votes will be taken on $M$ proposed ordinances. Each of the $N - 2$ assembly members except for the chairperson and the deputy chairperson will cast an affirmative vote or a negative vote on each proposed ordinance. The council will approve a proposed ordinance if a majority of the assembly members (i.e., more than or equal to $\left\lfloor \frac{N}{2} \right\rfloor$ assembly members) cast affirmative votes on it. Here, $\left\lfloor x \right\rfloor$ is the largest integer not exceeding $x$.

Mayor K, the mayor of JOI City, wants the council to approve as many proposed ordinances as possible. Mayor K collected information on assembly members. Mayor K knows, on each proposed ordinance, who will cast an affirmative vote and who will cast a negative vote.

Write a program which, given information of the votes of the assembly members, calculates, for each assembly member, the maximum possible number of proposed ordinances approved by the council if that assembly member is chosen as the chairperson.

Read the following data from the standard input.

$N$ $M$

$A_{1,1}$ $A_{1,2}$ $\cdots$ $A_{1,M}$

$A_{2,1}$ $A_{2,2}$ $\cdots$ $A_{2,M}$

$\vdots$

$A_{N,1}$ $A_{N,2}$ $\cdots$ $A_{N,M}$

Write $N$ lines to the standard output. The $i$-th line ($1 ≤ i ≤ N$) of output should contain the maximum possible number of proposed ordinances approved by the council if the assembly member $i$ is chosen as the chairperson.

• $3 ≤ N ≤ 300\,000$.
• $1 ≤ M ≤ 20$.
• $0 ≤ A_{i, j} ≤ 1$ ($1 ≤ i ≤ N$, $1 ≤ j ≤ M$).
• Given values are all integers.