题目描述

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 \le i \le N)$ will cast an affirmative vote on the proposed ordinance $j \ (1 \le j \le 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 $\lfloor \frac{N}{2} \rfloor$ assembly members) cast affirmative votes on it. Here, $\lfloor x \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 \le i \le 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.

题目大意

题目翻译

在 JOI 市议会中，有 $N$ 名议员，编号从 $1$ 到 $N$。议会将召开会议，议员们将对 $M$ 项提案进行表决，编号为 $1$ 到 $M$。如果 $A_{i,j}=1$，则议员 $i (1≤i≤N)$ 将对提案 $j (1≤j≤M)$ 表决肯定票。如果 $A_{i,j}=0$，则议员 $i$ 将对提案 $j$ 表决否定票。

JOI 市议会的程序如下所示。

• 在 $N$ 名议员中，通过抽签随机选择主席。

• 主席将在除了主席以外的其他 $N−1$ 名议员中选择副主席。

• 将对 $M$ 项提案进行表决。除了主席和副主席以外的其他 $N−2$ 名议员，每人对每个提案均投票支持或反对。如果大多数议员（即肯定票大于等于 $⌊\dfrac{N}{2}⌋$）投票赞成，则议会将批准该提案。其中 $⌊x⌋$ 表示不超过 $x$ 的最大整数。

市长 K 希望议会尽可能地批准更多的提案。市长 K 收集了议员的信息并知道每个议员在每个提案上的表决结果。

请编写程序，在给定议员投票信息的情况下，计算每个议员作为主席时议会可以批准的提案数量的最大可能值。

输入格式

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

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

输出格式

输出 $N$ 行。输出的第 $i$ 行（$1≤i≤N$）应包含议员 $i$ 作为主席时议会可以批准的提案数量的最大可能值。

样例解释 #1

• 假设议员 $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$。

Translate by

3 3
1 0 0
1 1 0
1 1 1

3
3
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

5
4
6
6

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

4 2
1 0
0 1
1 1
1 1

2
2
1
1

提示

【样例解释 #1】

• Let’s consider the case where the assembly member $1$ is chosen as the chairperson. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the first line.
• Let’s consider the case where the assembly member $2$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve three proposed ordinances, i.e., the proposed ordinances $1, 2, 3$. If the assembly member $3$ is chosen as the deputy chairperson, the council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $3$. Output $3$ in the second line.
• Let’s consider the case where the assembly member $3$ is chosen as the chairperson. If the assembly member $1$ is chosen as the deputy chairperson, the council will approve two proposed ordinances, i.e., the proposed ordinances $1, 2$. If the assembly member $2$ is chosen as the deputy chairperson, the council will approve one proposed ordinance, i.e., the proposed ordinance $1$. Therefore, the maximum number of proposed ordinances approved by the council is $2$. Output $2$ in the third line.

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

【样例解释 #2】

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

【样例解释 #3】

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

【样例解释 #4】

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

【数据范围】

对于所有测试数据，$3 \le N \le 3 \times 10 ^ 5$，$1 \le M \le 20$，$0 \le A_{i, j} \le 1$，保证所有输入均为整数。

子任务编号	分值	限制
$1$	$8$	$N \le 300$
$2$		$N \le 3000$
$3$	$6$	$M \le 2$
$4$	$19$	$M \le 10$
$5$	$15$	$M \le 14$
$6$	$22$	$M \le 17$
$7$		无