Maximizing Approved Ordinances in JOI City Council

In JOI City, there are \(N\) assembly members and \(M\) proposed ordinances. The vote of the assembly members on each ordinance is predetermined. When a meeting is held, a chairperson is chosen at random, and the chairperson then selects a deputy chairperson from the remaining members. Only the other \(N-2\) members cast votes on the ordinances.

An assembly member cast an affirmative vote (represented by 1) or a negative vote (represented by 0) on each proposed ordinance. The council approves an ordinance if at least \(\lfloor \frac{N}{2} \rfloor\) assembly members (note that this threshold is determined by the total number of members \(N\)) in the voting group cast an affirmative vote.

Mayor K wants to maximize the number of approved ordinances by strategically choosing the deputy chairperson. Given the voting information of each assembly member for each ordinance, you are to compute, for each assembly member when chosen as the chairperson, the maximum number of ordinances that can be approved if the chairperson selects the deputy optimally.

Problem Analysis

Let \(A_{i,j}\) be 0 or 1, where \(A_{i,j} = 1\) means that the assembly member \(i\) votes affirmatively on ordinance \(j\), and \(A_{i,j} = 0\) otherwise. For each proposed ordinance \(j\), let the total number of affirmative votes be \(T_j = \sum_{i=1}^{N} A_{i,j}\). When assembly member \(i\) is chosen as chairperson and assembly member \(j\) (\(i \neq j\)) is chosen as deputy, the votes considered are from the remaining \(N-2\) members. The effective number of affirmative votes for ordinance \(j\) then becomes:

[ V_{j} = T_j - (A_{i,j} + A_{j,j}). ]

An ordinance is approved if \(V_{j} \geq \lfloor \frac{N}{2} \rfloor\). For each possible chairperson \(i\), determine the deputy \(j\) (\(j \neq i\)) that maximizes the number of approved ordinances.

inputFormat

The input is given in the following format:

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]

Here, the first line contains two integers \(N\) and \(M\) denoting the number of assembly members and the number of proposed ordinances, respectively. Each of the next \(N\) lines contains \(M\) integers (0 or 1) representing the vote of an assembly member on each ordinance.

outputFormat

Output \(N\) lines. The \(i\)-th line should contain a single integer representing the maximum number of ordinances that can be approved if assembly member \(i\) is chosen as the chairperson.

sample

3 3
1 0 1
0 1 1
1 1 0

2
2
2