SPOJ Brasil

Dom Castellón é um ilusionista muito famoso, reconhecido pelas suas habilidades com truques de baralho. O último truque inventado por Dom Castellón é, também, bastante interessante. Ele faz um arranjo de baralho com as 13 cartas, não importando o naipe. As cartas são as tradicionais, ou seja, os nomes das cartas são ás, dois, três, quatro, cinco, seis, sete, oito, nove, dez, valete , dama e rei. O truque começa com todas as cartas organizadas uma sobre a outra, com a face para baixo, em uma pilha. Dom Castellón então começa a soletrar o nome de cada carta do baralho, de ás a rei. A cada letra soletrada, o ilusionista retira a carta do topo e a coloca embaixo da pilha. Ao soletrar a última letra de cada nome de carta, Dom Castellón retira a carta do topo e a mostra ao público. O espantoso é que a carta mostrada sempre corresponde àquela que acabou de ter o nome soletrado. Esta carta então é retirada do processo (ou seja, não volta à pilha) e o processo recomeça (o nome da próxima carta é soletrado) até que reste apenas o rei na pilha.

Por exemplo, suponha que as cartas estejam na pilha na sequinte ordem (do topo para baixo):

Q A 6 4 8 2 J 10 7 3 5 K 9

De acordo com a descrição do truque, Dom Castellón inicia soletrando o nome da primeira carta (às). Neste caso, Dom Castellón diz “a”, e coloca a dama embaixo da pilha. Ao soletrar “s”, vira a carta, e a carta às aparece, e é retirado da pilha. A pilha, agora, fica da seguinte maneira:

6 4 8 2 J 10 7 3 5 K 9 Q

Agora Dom Castellón soletra a palavra “dois”, e ao soletrar a letra “s”, vira a carta, e a carta dois aparece. E assim por diante, até restar apenas uma carta, que é o Rei.

Dom Castellón ficou tão famoso com esse truque que está agora sendo chamado para fazer demonstrações no mundo todo. Mas como o truque ficou conhecido, ele quer utilizar baralhos com mais cartas, como por exemplo o baralho de Tarot (14 cartas de cada naipe e 22 trunfos). Além disso, o truque depende não somente de quantas cartas há no baralho, mas do nome das cartas no país onde o truque vai ser executado. Assim, a pilha de cartas precisa ser arrumada de maneiras diferentes para cada conjunto de nomes que as cartas utilizadas recebem em cada país. Dom Castellón, então, veio pedir a sua ajuda para fazer um programa que, dados os nomes das cartas em uma determinada língua, descreva como deve ser montada a pilha para que o truque funcione.

Dados os nomes de um certo número de cartas, em ordem crescente (isto é, na ordem em que elas devem ser mostradas ao público durante o truque) determine qual é a ordem em que a pilha deve ser montada (de cima para baixo) para que o truque dê certo com aquele baralho naquele idioma.

Entrada

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha do conjunto de testes contém um número inteiro N que indica o número de cartas do baralho (2 ≤ N ≤ 300). Cada uma das N linhas seguintes contém o nome de uma carta. As cartas são dadas na ordem em que devem ser mostradas ao público durante o curso (o nome na primeira linha corresponde à carta que deve ser mostrada em primeiro lugar, o nome na segunda linha à carta mostrada em segundo lugar, e assim por diante). Cada nome de carta tem no máximo 100 caracteres e é composto somente por letras minúsculas.

Saída

Seu programa deve imprimir, na saída padrão, a ordem em que a pilha deve ser montada, de cima pra baixo. As cartas devem ser descritas com os mesmos nomes dados na entrada, sendo uma carta por linha.

Exemplo

Entrada:
13
as
dois
tres
quatro
cinco
seis
sete
oito
nove
dez
valete
dama
rei

Saída:
dama
as
seis
quatro
oito
dois
valete
dez
sete
tres
cinco
rei
nove

Entrada:
5
primeira
segunda
terceira
quarta
quinta

Saída:
segunda
quarta
primeira
terceira
quinta