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 ≤ n ≤ 10⁵. 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 ≤ m ≤ 10⁵. 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 ≤ n ≤ 10³ i 0 ≤ m ≤ 10³.