E - Skriptá

Doktorand Marek sa po odovzdaní dizertačnej práce venujúcej sa algoritmom usporiadania rozhodol všetky svoje doteraz získané (a zapísané) materiály vydať ako skriptá. Keď sa však teraz pozrel na všetky materiály čo vytvoril, tak s hrôzou zistil, že nedodržal jednotnú terminológiu (na začiatku svojho štúdia sa stále hovorilo o triedení, neskôr sa za správny pojem začalo považovať usporiadanie). V rámci skrípt je z didaktických dôvod potrebné zachovať jednotnosť všetkých termínov, a tak musí nesprávne termíny nahrádzať novými. Keďže má medzi svojimi kamarátmi aj Vás a vie, že ste veľmi zruční programátori, dohodol sa s Vami, že mu napíšete program, ktorý jeho skriptá upraví.

Úloha

Marek si spísal zoznam termínov (slov), ktoré potrebuje v celej práci nahradiť. Vytvoril dvojice slov - jedno staré nesprávne slovo, a jedno nové vhodné, ktorým treba to staré nahradiť.

Napíšte program, ktorý načíta zoznam dvojíc slov a vstupný text, a následne vo vstupnom texte všetky výskyty nesprávnych slov nahradí ich novými, vhodnými "ekvivalentmi".

Vstup

V prvom riadku súboru sa nachádza prirodzené číslo N (1 ≤ N ≤ 100 000), ktoré udáva počet zamieňaných slov.

Nasleduje N riadkov, pričom v každom sa nachádzajú vždy dve slova oddelené medzerou. Slová sú tvorené iba z veľkých písmen anglickej abecedy. Prvé slovo v každom z týchto N riadkov je nesprávne, druhé je jeho náhrada.

Od riadku N+2 až do konca súboru nasleduje samotný text skrípt. Text je tvorený iba z veľkých písmen anglickej abecedy a medzier (a koncov riadkov), pričom súvislé úseky písmen tvoria jednotlivé slová. Môžete predpokladať, že žiadné slovo nebude dlhšie ako 255 písmen a že žiadne dve nesprávne slová nebudú rovnaké.

Výstup

Výstupom programu je text, v ktorom boli všetky nesprávne slová nahradené ich vhodnejšími ekvivalentmi. Zvyšok súboru musí zostať bez zmeny, vrátane rovnakých medzier a rozdelenia slov do riadkov.

Príklad

Vstup:

3
TRIEDENIE USPORIADANIE
VKLADANIM VSUVANIM
TRIEDIT USPORIADAT
TRIEDENIE VKLADANIM JE JEDNO Z NAJJEDNODUCHSICH
TOTO TRIEDENIE MA KVADRATICKU ZLOZITOST

Výstup:

USPORIADANIE VSUVANIM JE JEDNO Z NAJJEDNODUCHSICH
TOTO USPORIADANIE MA KVADRATICKU ZLOZITOST