B - Most Minority Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

人 1,2,\dots,N ( N は奇数 ) が、 M 回の 0 か 1 かを選択する投票を行いました。
各人の各回の投票は N 個の長さ M の 0, 1 からなる文字列 S_1,S_2,\dots,S_N として与えられ、 S_i の j 文字目は人 i の j 回目の投票への内容を表します。

各回の投票で、少数派であった人は 1 点を得ます。
より厳密には、次のルールで得点が与えられます。

  • その回の投票で 0 を選択した人が x 人、 1 を選択した人が y 人いたとします。
    • x=0 または y=0 である場合、その投票では全員に 1 点が与えられる。
    • そうでなく x<y である場合、その投票で 0 に投票した人のみに 1 点が与えられる。
    • そうでない場合、その投票で 1 に投票した人のみに 1 点が与えられる。
    • なお、 N が奇数であることから x=y となることはないことに留意してください。

M 回の投票を終えた後、それらの投票における合計の得点が最も高い人を全員求めてください。

制約

  • N は 1 \le N \le 99 を満たす 奇数
  • M は 1 \le M \le 100 を満たす整数
  • S_i は長さ M の 0, 1 からなる文字列

入力

入力は以下の形式で標準入力から与えられる。

N M
S_1
S_2
\vdots
S_N

出力

得点が最も高い人の番号を全て、 番号の昇順に 空白区切りで出力せよ。

入力例 1

3 5
11100
10101
01110

出力例 1

2 3

このケースでは、 3 人が 5 回の投票を行いました。

  • 1 回目の投票では人 1 が 1 、人 2 が 1 、人 3 が 0 に投票しました。よって、人 3 のみが 1 点を得ます。
  • 2 回目の投票では人 1 が 1 、人 2 が 0 、人 3 が 1 に投票しました。よって、人 2 のみが 1 点を得ます。
  • 3 回目の投票では人 1 が 1 、人 2 が 1 、人 3 が 1 に投票しました。よって、全員が 1 点を得ます。
  • 4 回目の投票では人 1 が 0 、人 2 が 0 、人 3 が 1 に投票しました。よって、人 3 のみが 1 点を得ます。
  • 5 回目の投票では人 1 が 0 、人 2 が 1 、人 3 が 0 に投票しました。よって、人 2 のみが 1 点を得ます。

この結果、人 1 は合計 1 点、人 2 は合計 3 点、人 3 は合計 3 点を得ました。
よって、人 2,3 が合計の得点が最も高い人です。これらを番号の昇順に出力してください。

入力例 2

5 4
0000
0000
0000
0000
0000

出力例 2

1 2 3 4 5

入力例 3

7 8
11010011
01000000
01111100
10111000
10011110
10100101
10010110

出力例 3

1 2 3

Score : 200 points

Problem Statement

People 1,2,\dots,N (where N is odd) conducted M votes where each person chooses either 0 or 1.
Each person's vote for each round is given as N strings S_1,S_2,\dots,S_N of length M consisting of 0 and 1, where the j-th character of S_i represents person i's vote content for the j-th vote.

In each vote, people who were in the minority receive 1 point.
More precisely, points are given according to the following rules:

  • Suppose x people chose 0 and y people chose 1 in that vote.
    • If x=0 or y=0, everyone receives 1 point for that vote.
    • Otherwise, if x<y, only people who voted 0 in that vote receive 1 point.
    • Otherwise, only people who voted 1 in that vote receive 1 point.
    • Note that since N is odd, x=y never occurs.

After finishing M votes, find all people who have the highest total score from those votes.

Constraints

  • N is an odd number satisfying 1 \le N \le 99.
  • M is an integer satisfying 1 \le M \le 100.
  • S_i is a string of length M consisting of 0 and 1.

Input

The input is given from Standard Input in the following format:

N M
S_1
S_2
\vdots
S_N

Output

Output all person numbers with the highest score in ascending order of person number, separated by spaces.

Sample Input 1

3 5
11100
10101
01110

Sample Output 1

2 3

In this case, three people conducted five votes.

  • In the 1st vote, person 1 voted 1, person 2 voted 1, person 3 voted 0. Thus, only person 3 receives 1 point.
  • In the 2nd vote, person 1 voted 1, person 2 voted 0, person 3 voted 1. Thus, only person 2 receives 1 point.
  • In the 3rd vote, person 1 voted 1, person 2 voted 1, person 3 voted 1. Thus, everyone receives 1 point.
  • In the 4th vote, person 1 voted 0, person 2 voted 0, person 3 voted 1. Thus, only person 3 receives 1 point.
  • In the 5th vote, person 1 voted 0, person 2 voted 1, person 3 voted 0. Thus, only person 2 receives 1 point.

As a result, person 1 received a total of 1 points, person 2 received a total of 3 points, and person 3 received a total of 3 points.
Therefore, persons 2 and 3 have the highest total score. Output these in ascending order of person number.

Sample Input 2

5 4
0000
0000
0000
0000
0000

Sample Output 2

1 2 3 4 5

Sample Input 3

7 8
11010011
01000000
01111100
10111000
10011110
10100101
10010110

Sample Output 3

1 2 3