Perdent els papers X10383

Un supermercat està a punt d’obrir i els clients fan cua davant la porta. Tothom vol ser el primer d’entrar per adquirir prou paper de vàter per cobrir les seves necessitats. La competència arriba a tal punt que els clients es van colant entre si mentre fan la cua.

Sabent quin és l’ordre inicial a la cua i els avançaments entre els clients, i tenint en compte que els avançaments estan prohibits dintre del supermercat (per assegurar prou distància entre clients), en quin ordre arribaran a la tan volguda secció higiènica?

Entrada

L’entrada comença amb el nombre de clients $n$ a la primera línia, amb $1 \le n \le 10^5$. Segueixen $n$ línies amb el nom dels $n$ clients en l’ordre inicial a la cua, de primer a últim. Els noms són paraules diferents amb entre 1 i 10 lletres minúscules i majúscules. Segueix una línia amb el nombre d’avançaments $m$, amb $0 \le m \le 10^5$. Finalment, cadascuna de les $m$ línies següents conté dos noms de clients $s$ i $t$, indicant que $s$ acaba d’avançar a $t$. Es garanteix que tant $s$ com $t$ estan a la cua, i que en el moment de l’avançament $s$ està just darrere de $t$.

Sortida

Escriviu $n$ línies amb tots els clients en l’ordre d’arribada.

Observació

Podeu aconseguir un 25% dels punts per a casos on $1 \le n \le 10^3$ i $0 \le m \le 10^3$.