澳大利亚投票系统要求选民们将所有候选人按愿意选择的程度排序,一张选票就是一个排序。一开始,每张选票的首选项将被统计。若有候选人得票超过50%,他将直接胜出:否则,所有并列得票最低的候选人出局,而那些将出局候选人排在第一位的选票将被重新统计为排名最高的未出局候选人。这一筛选过程将持续进行,直到某个候选人得到超过50%的选票,或所有候选人得票相同。
输入第一行包含一个正整数,代表测试数据组数。然后是一个空行,接下来是数据。每两组测试数据间用空行隔开。
每组数据第一行为一个整数n≤20,代表候选人数目。接下来n行按顺序给出每个候选人的名字,最长80个字符,可以是任何可打印字符。接下来是至多1000行,每行描述一张选票的内容。每张选票包含1到n的某一排列。第一个为首选,第二个次选,以此类推。
对于每组数据,输出数据可能是单独一行,即胜出者的名字;或者若干行,分别包含所有平局的候选人。每两组数据间用一个空行隔开。
1 3 John Doe Jane Smith Jane Austen 1 2 3 2 1 3 2 3 1 1 2 3 3 1 2
John Doe