선거

$M$명으로 이루어진 유권자 집단의 투표 선호도가 주어질 때, $1$번부터 $N$번까지 번호가 매겨진 $N$명의 후보 중에서 선거의 당선자를 결정하라. 이 문제에서 $M$명의 유권자는 $G$개의 "그룹"으로 나뉘며, 같은 그룹에 속한 유권자들은 모두 동일한 투표 선호도를 가진다. 각 그룹의 선호도는 가장 선호하는 후보부터 가장 선호하지 않는 후보까지 순서대로 나열하여 주어진다. 선거 결과는 즉석 결선투표(instant-runoff voting) 방식으로 결정된다.

이 방식에서는 먼저 모든 유권자가 현재 가장 선호하는 후보(1순위)를 집계하여, 득표가 가장 적은 후보를 탈락시킨다. 득표수가 같아 동점이 발생하면, 그중 번호가 가장 큰 후보를 탈락시킨다. 그런 다음 탈락한 후보를 모든 유권자의 선호 목록에서 제거하고, 다시 득표가 가장 적은 후보를 탈락시킨다. 이 과정을 후보가 한 명만 남을 때까지 반복하며, 마지막에 남은 후보가 당선자이다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $G$와 $N$이 주어진다 ($2 \le N \le 5$, $1 \le G \le 20$). 이어지는 $G$개의 줄은 각각 $M_i\ a_{i1}\ a_{i2}\ \dots\ a_{iN}$ 형식이며, $1 \le M_i \le 20$이고 $a_{i1}, \dots, a_{iN}$은 정수 $1, \dots, N$의 순열이다. $M_i$는 $i$번째 그룹에 속한 유권자 수이고, $a_{i1}, \dots, a_{iN}$은 그 그룹이 가장 선호하는 후보부터 가장 선호하지 않는 후보까지의 순서이다. 입력의 끝은 $G = N = 0$인 테스트 케이스로 표시되며, 이 케이스는 처리하지 않는다.

각 테스트 케이스에 대해 선거의 당선자를 한 줄에 하나씩 출력한다.