URI Online Judge | 1586

Tug of War

By Leandro Zatesko, UFFS BR Brazil

Timelimit: 1

At 2013 ACM ICPC Regional South America/Brazil Contest in Uberlândia, during a period of leisure, Prof. Carlinhos (USP) came up with an activity for all the students. He first organised the students in ascending lexicographical order, considering only the first name and ignoring diacritics. Then, he drew a student and assembled two teams, A and B: team A would consist of those students in order up to the drawn student; team B would in turn consist of those students who came after the drawn student in the order. Both teams would compete in a traditional tug of war, and the winners would win a coffee.

Many curious things Prof. Carlinhos realised that day:

709 = 76 + 101 + 97 + 110 + 100 + 114 + 111 = ‘L’ + ‘e’ + ‘a’ + ‘n’ + ‘d’ + ‘r’ + ‘o’

Is there any student Prof. Carlinhos could draw so that the teams A and B would tie?

Input

The input consists of many test cases. The first line of each test case consists of a single integer N (1 ≤ N ≤ 105), which represents the number of students. Follow then N lines, each one containing the first name of the student. The names of the students are given according to the ascending lexicographical order, and at least 1 and at most 10 latin letters form the name of a student. There is no test case with two students with the same first name, and the first letter of a name is always capital, while the other letters are small. N = 0 ends the input.

Output

Print the name of the student who, if drawn, would make the teams A and B to tie. If there is no such student, just print the line: “Impossibilidade de empate.” (without the quotation marks).

Sample Input Sample Output

9
Ana
Bruna
Cro
Digory
Emerson
Fiaror
Geomar
Iago
Zacarias
14
Aule
Este
Lorien
Mandos
Manwe
Nessa
Nienna
Orome
Tulkas
Ulmo
Vaire
Vana
Varda
Yavanna
0

Emerson
Impossibilidade de empate.