순위 선택 투표

순위 선택 투표(즉시 결선 투표라고도 한다)는 샌프란시스코와 오클랜드의 일부 시장 선거에서 쓴다. 유권자는 후보 한 명만 고르는 대신 최대 세 명까지 1순위, 2순위, 3순위로 적는다.

개표를 시작할 때는 1순위 표만 센다. 한 후보가 1순위 표의 과반을 확보하면 그 후보가 곧바로 당선된다. 과반은 아직 유효한 표가 하나라도 남은 투표용지 수의 절반을 넘는 것을 뜻한다.

첫 집계에서 과반이 나오는 경우는 드물다. 2011년 11월 8일 샌프란시스코 시장 선거의 공식 후보는 16명이었고, 최종 당선자인 Ed Lee의 1순위 득표율은 31%에 그쳤다. 과반을 얻은 후보가 없으면 1순위 표가 가장 적은 후보를 모두 한꺼번에 탈락시킨다. 탈락한 후보의 이름은 모든 투표용지에서 지우고, 그 아래에 적힌 순위를 한 칸씩 끌어올려 빈자리를 메운다.

Phil Ting이 1순위 표를 가장 적게 받았다고 하자. 그의 이름이 적힌 투표용지에서는 그 이름을 지운다. Phil Ting만 적힌 투표용지는 남는 표가 없으므로 버린다. 그를 1순위로 적은 투표용지에서는 2순위가 1순위가 되고 3순위가 2순위가 된다.

남은 투표용지의 1순위 표에서 한 후보가 과반을 얻을 때까지 이 과정을 반복한다. 2011년 샌프란시스코 선거는 탈락을 12번 반복한 뒤 Ed Lee가 남은 1순위 표의 61%를 얻어 마무리됐다.

후보는 아직 유효한 투표용지에 문자가 적혀 있는 사람 전부이고, 몇 순위에 적혔는지는 상관없다. 2순위나 3순위로만 적힌 후보의 1순위 표는 0표여서 가장 적으므로, 탈락이 일어나는 회차에 함께 탈락한다.

한 회차가 끝났을 때 남은 후보의 1순위 표가 모두 같으면 전부 최저 득표로 묶여 함께 탈락하고, 모든 투표용지가 비어 당선자가 나오지 않는다.

첫 줄에 시나리오 수 $T$가 주어진다 ($1 \le T \le 100$).

각 시나리오의 첫 줄에는 투표용지 수 $n$이 주어진다 ($1 \le n \le 100000$). 이어지는 $n$개의 줄에는 투표용지가 한 줄에 하나씩, 대문자 1개에서 3개로 이루어진 문자열로 주어진다. 문자 하나가 후보 한 명이다. 첫 번째 문자가 1순위, 두 번째 문자가 있으면 2순위, 세 번째 문자가 있으면 3순위다. 한 투표용지에 같은 후보가 두 번 적히는 일은 없다.

각 시나리오마다 후보가 어떻게 탈락했는지 한 줄로 정리해 출력한다.

탈락 없이 당선자가 바로 정해지면 그 후보의 문자만 출력한다. A처럼 쓴다.

탈락이 한 번 이상 필요하면 회차 순서대로 ->로 이어 붙이고 마지막에 당선자의 문자를 쓴다. EF -> D -> C -> B는 첫 회차에 E와 F가, 둘째 회차에 D가, 셋째 회차에 C가 탈락하고 B가 당선됐다는 뜻이다. 같은 회차에 탈락한 후보는 아무 기호도 넣지 않고 알파벳 순으로 붙여 쓴다.

탈락을 반복해도 당선자가 나오지 않으면 마지막을 문자 대신 no winner로 끝낸다. DE -> A -> BCF -> no winner는 두 회차를 거친 뒤 B, C, F의 1순위 표가 같아져서 셋째 회차에 세 후보가 모두 탈락하고 남은 후보가 없다는 뜻이다.

-> 양쪽에는 공백을 정확히 하나씩 두고, 줄 끝에는 공백을 남기지 않는다.