By Leandro Zatesko, UFFS Brazil
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?
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.
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|