Les Falles de València són una de les festes més reconeixibles a nivell mundial. No només estan considerades una festa d'Interès Turístic Internacional, sinó que la Unesco les va inscriure, el 2016, a la seva Llista Representativa del Patromoni Cultural Immaterial de la Humanitat.

Se celebren entre el 14 i el 19 de març i un dels seus principals atractius passa amb la crema de les falles. Una falla és una obra d'artesania composta principalment de fusta, cartró i altres materials inflamables, que es crea per ser cremada a la festa de Sant Josep, patró dels fusters. Normalment està composta d'una figura central de diversos metres d'alçada, envoltada de figures més petites conegudes com a ninots (ninot en castellà).

Abans de la crema de les falles es fa l'Exposició dels Ninots, on els visitants poden votar pels seus preferits. Cada any, dos ninots (infantil i adult) se salven gràcies a això de la crema, convertint-se cadascun en un ninot indultat (ninot indultat).

Input Format

Cada cas de prova comença amb un número \(1 ≤ n ≤ 1.000\) indicant la quantitat de votacions realitzades entre els visitants a l'exposició dels Ninots. A continuació apareixen els \(n\) vots, ocupant potencialment diverses línies.

Cada vot està compost per una cadena de caràcters \(c\) de no més de 20 lletres angleses amb el nom del ninot. Si és un ninot infantil totes les lletres estaran en minúscula i si és un ninot adult totes estaran en majúscula.

L'entrada acaba amb un 0 que no s'ha de processar.

Constraints

• \(1 ≤ n ≤ 1.000\)
• \(0 ≤ length(c) ≤ 20\)
• Es garanteix que en cada cas de prova hi haurà almenys un ninot de cada tipus.
• Es garanteix que no hi haurà ninots amb els noms empate o EMPATE.

Output Format

Per cada cas de prova el programa escriurà els noms del ninot infantil i adult guanyadors del premi per ser els més votats a la seva categoria, en aquest ordre i separats per un espai. S'utilitzarà el mateix esquema d'ús de lletres majúscules que a l'entrada.

Si en una de les categories es produeix empat, s'escriurà empate o EMPATE per a la categoria infantil i adulta respectivament.

Test Case 1

Input

2
QUARTEXTRAMURS najordana
5
condealtea GUANYARDINES
antigadecampanar QUARTEXTRAMURS GUANYARDINES
0

Output

najordana QUARTEXTRAMURS
empate GUANYARDINES

Test Case 2

Hidden: this is a private test case!