beecrowd | 1586

# Tug of War

By Leandro Zatesko, UFFS 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:

• The strength of each student, when placed right in front the adversary (position 1), was exactly equal to the sum of the values corresponding to the characters in ASCII table of the first name of student. Thus, the strength of student Leandro, if placed in position 1 of a team (no matter A or B), would be equal to:

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

• The farther from adversary team, less intimidated — and, in consequence, stronger — a student gets. More specifically, a student in position 2 of a team was twice stronger than he or she would be if had been placed in position 1. In position 3, three times etc. Positions of both teams are counted starting the counting in 1 at the closest position to the adversary team. For example, if student Leandro was placed in position 3 of a team, he would have strength equal to 3 × 709 = 2127.
• The strength of a team was equal to the sum of the strengths of all its team members. Nevertheless, if the strength of team A was greater than the strength of team B, team A certainly would win. However, if it was less than, team B certainly would. Finally, if both strengths were equal, the teams would be tied.

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.