The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – CouncilCouncil
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 Ai, j = 1, the assembly member i (1 ≤ i ≤ N) will cast an aﬃrmative vote on the proposed ordinance j(1 ≤ j ≤ M). If Ai, 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 thechairperson.
3. The votes will be taken on M proposed ordinances. Each of the N − 2 assembly members except for thechairperson and the deputy chairperson will cast an aﬃrmative 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 N2 assembly members) cast aﬃrmative votes on it. Here, ⌊x⌋ 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 aﬃrmative 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.

Input
Read the following data from the standard input.
NMA1,1 A1,2 · · · A1,MA2,1 A2,2 · · · A2,M..
.
AN,1 AN,2 · · · AN,M

Council– 1 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – Council

OutputWrite 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.

Constraints• 3 ≤ N ≤ 300 000.
• 1 ≤ M ≤ 20.
• 0 ≤ Ai, j ≤ 1 (1 ≤ i ≤ N, 1 ≤ j ≤ M).
• Given values are all integers.

Subtasks
1. (8 points) N ≤ 300.
2. (8 points) N ≤ 3000.
3. (6 points) M ≤ 2.
4. (19 points) M ≤ 10.
5. (15 points) M ≤ 14.
6. (22 points) M ≤ 17.
7. (22 points) No additional constraints.

Council– 2 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – Council

Sample Input and Output
Sample Input 1Sample Output 13 33

1 0 0

3

1 1 021 1 1• Let’s consider the case where the assembly member 1 is chosen as the chairperson. If the assemblymember 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, themaximum 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, thecouncil 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 assemblymember 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 councilwill approve one proposed ordinance, i.e., the proposed ordinance 1. Therefore, the maximum numberof proposed ordinances approved by the council is 2. Output 2 in the third line.
This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6, 7.
Sample Input 2Sample Output 24 1251 1 1 0 1 1 0 1 0 1 1 041 1 0 1 1 0 1 1 1 1 1 060 0 1 1 1 0 0 0 0 0 1 161 0 0 0 1 1 1 1 1 0 0 0This sample input satisfies the constraints of Subtasks 1, 2, 5, 6, 7.

Council– 3 / 4

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)
Contest 2 – Council
Sample Input 3

Sample Output 3

16 4

30 0 0 0

30 0 0 1

30 0 1 0

20 0 1 1

30 1 0 0

20 1 0 1

20 1 1 0

10 1 1 13

1 0 0 02

1 0 0 1

21 0 1 0

11 0 1 1

21 1 0 0

11 1 0 1

11 1 1 001 1 1 1This sample input satisfies the constraints of Subtasks 1, 2, 4, 5, 6, 7.
Sample Input 4

Sample Output 44 2

2

1 0

20 1

1

1 1

1

1 1
This sample input satisfies the constraints of all the subtasks.

Council– 4 / 4