Look for the Winner!

Time limit2sMemory limit512 MB

Summary

Given votes counted in order, report the earliest prefix after which one candidate's lead cannot be overtaken from remaining votes, or TIE.

Level: Easy3 of 10
Topics: Array, Simulation, Greedy
Solved: No attempts yet

Problem

The citizens of TKB City love elections and vote counting. Today they hold an election for the next chairperson of the electoral commission. Voting has just closed and counting is about to start. The citizens want to know the winner as early as possible while the votes are counted.

The candidate with the most votes becomes the next chairperson. Suppose there are three candidates A, B, and C and ten votes. Suppose also that six of the ten votes have been counted and the counts of A, B, and C are four, one, and one. At this moment every candidate can still receive four more votes, so anyone can still win. If the seventh counted vote is cast for A, then A is certain to win: A already has five votes and B or C can end with at most four. In this example the citizens know the winner as soon as the seventh vote is counted.

Write a program that reads the counted votes one by one, finds the winner, and reports after how many votes the winner becomes certain.

Input

The input has at most 1500 datasets. Each dataset is two lines in this format.

n
c1 c2 ... cn

The first line holds $n$ , the number of votes, a positive integer no greater than 100. The second line holds the $n$ votes separated by single spaces. Each $c_i$ ( $1 \le i \le n$ ) is one uppercase letter from A to Z and names the candidate who received the $i$ -th vote. Counting runs in the given order from $c_1$ to $c_n$ .

Assume that at least two candidates stand, even when every vote is cast for one candidate.

A line containing a single zero marks the end of the input.

Output

For each dataset print one line. If the election does not end in a tie, print the uppercase letter $c$ of the winner and an integer $d$ separated by one space, where $d$ is the number of counted votes after which the winner is certain. If the largest number of votes is shared by two or more candidates, print TIE instead.

The winner is certain once no distribution of the remaining votes lets another candidate reach the leader's count. Since at least two candidates stand, a candidate with no votes so far can still receive the remaining votes.

Examples4

Example 1

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

Expected output

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

Example 2
Input
```
1
Z
2
Q Q
0
```
Expected output
```
Z 1
Q 2
```

Example 3

Input

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

Expected output

TIE
TIE
TIE

Example 4

Input

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

Expected output

A 3
A 5
A 5