승자를 찾아라!

시간 제한2초메모리 제한512 MB

요약

투표를 순서대로 세면서 남은 표로 다른 후보가 따라잡을 수 없게 되는 최소 시점의 당선자를 판별하고, 동점이면 TIE를 출력한다.

난이도: 쉬움10점 중 3점
유형: 배열, 시뮬레이션, 그리디
정답자: 아직 제출이 없습니다

문제

TKB 시의 시민은 선거와 개표를 아주 좋아한다. 오늘은 선거관리위원회의 다음 위원장을 뽑는 선거가 열렸다. 투표가 방금 끝났고 이제 개표가 시작된다. 시민들은 개표가 진행되는 동안 승자를 최대한 빨리 알고 싶어 한다.

표를 가장 많이 받은 후보가 다음 위원장이 된다. 후보가 A, B, C 세 명이고 표가 열 장인 경우를 생각해 보자. 열 장 가운데 여섯 장을 개표했고 A, B, C의 득표수가 각각 4, 1, 1이라고 하자. 이 시점에서는 모든 후보가 남은 네 표를 받을 가능성이 있으므로 누구나 아직 승자가 될 수 있다. 그러나 일곱 번째로 개표한 표가 A의 표라면 A는 5표가 되고 B와 C는 끝까지 가도 4표를 넘지 못하므로 A의 승리가 확정된다. 이 예에서 시민들은 일곱 번째 표를 개표하는 순간 승자를 알게 된다.

개표되는 표를 하나씩 읽어 승자를 찾고, 몇 번째 표까지 개표했을 때 승자가 확정되는지 구하는 프로그램을 작성하라.

입력

입력은 최대 1500개의 데이터셋으로 이루어진다. 각 데이터셋은 다음 형식의 두 줄이다.

n
c1 c2 ... cn

첫 줄의 $n$ 은 표의 개수로, 100 이하의 양의 정수다. 둘째 줄에는 $n$ 장의 표가 공백 하나로 구분되어 주어진다. 각 $c_i$ ( $1 \le i \le n$ )는 A부터 Z까지의 대문자 한 글자이며, $i$ 번째 표를 받은 후보를 나타낸다. 개표는 $c_1$ 부터 $c_n$ 까지 주어진 순서대로 진행한다.

모든 표가 한 후보에게 몰린 경우에도 후보는 최소 두 명이라고 가정한다.

입력의 끝은 0 하나만 있는 줄로 표시한다.

출력

데이터셋마다 한 줄을 출력한다. 선거가 동점으로 끝나지 않으면 승자를 나타내는 대문자 $c$ 와 정수 $d$ 를 공백 하나로 구분해 출력한다. $d$ 는 몇 번째 표까지 개표했을 때 승자가 확정되는지를 뜻한다. 최다 득표가 동점으로 끝나면 대신 TIE를 출력한다.

남은 표를 어떻게 나누어도 다른 후보가 선두의 득표수에 도달하지 못하는 순간 승자가 확정된다. 후보는 최소 두 명이므로 아직 한 표도 받지 못한 후보도 남은 표를 받을 수 있다.

예제4

예제 1

입력

1
A
4
A A B B
5
L M N L N
6
K K K K K K
6
X X X Y Z X
10
A A A B A C A C C B
10
U U U U U V V W W W
0

예상 출력

A 1
TIE
TIE
K 4
X 5
A 7
U 8

예제 2
입력
```
1
Z
2
Q Q
0
```
예상 출력
```
Z 1
Q 2
```

예제 3

입력

2
A B
3
A B C
6
A A B B C C
0

예상 출력

TIE
TIE
TIE

예제 4

입력

3
A B A
5
A B A B A
5
A B B A A
0

예상 출력

A 3
A 5
A 5