← 返回题目列表

Codeforces · 570/A

A. 选举

中文机器翻译题面 查看原题

Byalechinsk 国家正在进行选举,涉及 n 名候选人。该国由 m 个城市组成。我们知道每个城市有多少人投票给每位候选人。

该国的选举制度非常不寻常。第一阶段选举按每个城市计票:假设每个城市中得票数最高的候选人获胜,如果有多个候选人获得最多票数,则以指数较小者获胜。

第二阶段选举的获胜者按城市数相同的原则确定:获胜城市数最多的候选人为选举获胜者,获得最多城市数的候选人中指数较小的获胜者。

确定谁将赢得选举。

输入

输入的第一行包含两个整数 n, m (1 ≤ n, m ≤ 100) — 分别是候选人数和城市数。

接下来的 m 行每行包含 n 个非负整数,第 i 行中的第 j 个数字 aij (1 ≤ j ≤ n, 1 ≤ i ≤ m, 0 ≤ aij ≤ 109) 表示候选人 j 在城市 i 的得票数。

保证所有城市的总人数不超过109人。

输出

打印一个数字——赢得选举的候选人的索引。候选者从 1 开始索引。

示例

输入 #1

3 3
1 2 3
2 3 1
1 2 1

输出 #1

2

输入 #2

3 4
10 10 3
5 1 6
2 2 2
1 5 7

输出 #2

1

注意

第一个样本测试注意事项。第一阶段,城市1选择候选人3,城市2选择候选人2,城市3选择候选人2。获胜者是候选人2,他获得了2票。

第二个样本测试注意事项。第一阶段,城市1的候选人1和2获得相同的最大票数,但候选人1的指数较小,因此该城市选择候选人1。城市2选择候选人3。城市3选择候选人1,因为每个人的票数相同,而1的指数最小。城市 4 选择了候选城市 3。在第二阶段,相同数量的城市选择了候选城市 1 和 3。获胜者是候选城市 1,即索引较小的城市。