题目描述

题目翻译

在 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$ 作为主席时议会可以批准的提案数量的最大可能值。

题目大意

题目翻译

在 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, 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$		无