003 - 当選者を探せ!

Problem B

TKB 市民は選挙と開票が大好きなことで有名である． 今日は選挙管理委員会の次期委員長を決める選挙の日である． 今投票が終わり，開票が始まろうとしている． TKB 市民は，開票中に少しでも早く当選者を知りたいと強く望んでいる．

もっとも多くの票を得た候補者が次期委員長に選出される． たとえば，候補者が A, B, C の 3 人で，投票数が 10 票の場合を考える． そして，10 票のうち 6 票までの開票が行われ，A, B, C がそれぞれ 4 票，1 票，1 票を得たとする． この時点では，すべての候補者があと 4 票を得る可能性があり，全員が当選する可能性を残している． しかし，もし次に開いた票が A に投じられたものなら，A の当選が確定する． なぜならば，ここまでの A の得票は 5 票となり，最終的な B と C それぞれの得票は，高々 4 票にしかならないからである． この例では，7 票目を開票した時点で，TKB 市民は当選者を知ることができる．

そこで，開票中の票を一つずつ順番に受け取り，当選者が誰であるかとそれがいつ確定したかを求めるプログラムを作成してほしい．

Input

入力は最大で 1500 個のデータセットからなる． 各データセットは 2 行からなり次のような形式である．

n
c1 c2 … cn

1 行目の整数 n は投票数を表し，100 以下の正整数である． 2 行目が投票された n 票を表す． 各 c_i（1 ≤ i ≤ n）は，一つの英大文字（'A' から 'Z' のうちの一つ）であり，空白文字で区切られる． これは i 番目の票が投じられた候補者を表す． 開票は，c₁ から c_n まで出現順に行われる．

たとえ，すべての票が一人の候補者に集中していても，候補者は二人以上いると仮定すること．

入力の終わりは，1 個のゼロだけからなる行で表される．

Output

各データセットについて，選挙が引き分けに終わらないなら，空白文字 1 個で区切られた英大文字 c と整数 d からなる行を出力せよ． ここで，c は当選者を表す． d は何番目の票を開票した時点ではじめて当選が確定したかを表す． それ以外の場合，すなわち選挙が引き分けに終わった場合は，`TIE' のみからなる行を出力せよ．

Sample Input

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

Output for the Sample Input

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