replace

Una dintre cele mai importante operaţii în timpul procesării unui text este operaţia find&replace, de găsire a unui şir şi de înlocuire a acestuia cu un alt şir specificat. Vom considera pentru problema noastră un caz special: acela în care dorim să facem o serie de înlocuiri într-o linie de text, utilizând un set de reguli. Fiecare regulă specifică şirul care trebuie găsit şi şirul cu care se va înlocui acesta. Se porneşte cu prima regulă, căutându-se şirul de înlocuit şi înlocuindu-se cu cel precizat. Se continuă cu prima regulă până nu se mai poate aplica deoarece şirul de înlocuit nu mai este găsit. Se procedează la fel cu celelalte reguli în ordinea în care sunt date. În plus se precizează următoarele:

• pentru detectarea şirului de înlocuit se pleacă de fiecare dată de la începutul textului;
• după terminarea aplicării unei reguli, nu se mai revine la ea;
• operaţiile se desfăşoară considerând diferite literele mari de literele mici (case-sensitive).

Cerinţă

Dat un set de reguli şi textul în care trebuie realizate înlocuirile, să se determine forma finală a textului.

Date de intrare

Fişierul de intrare replace.in conţine pe prima linie un număr natural $N$ reprezentând numărul de reguli. Următoarele $2 \cdot N$ linii conţin perechi de şiruri, primul şir din pereche fiind şirul care se caută, iar pe rândul imediat următor şirul cu care trebuie înlocuit acesta. Ultimul rând al fişierului de intrare conţine textul în care se vor face înlocuirile.

Date de ieşire

Fişierul de ieşire replace.out va conţine o singură linie pe care va fi scris textul obţinut după aplicarea celor $N$ reguli de înlocuire.

Restricții și precizări

• $0 \leq N \leq 10$
• textul conţine caractere cu codul ASCII cuprins în intervalul $[32, 127]$;
• textul iniţial şi cel final au maxim $255$ caractere;
• lungimea maximă a şirului în timpul transformărilor nu va depăşi $30 \ 000$ caractere;
• şirurile care se caută precum şi cele care le vor înlocui au maxim $80$ caractere;
• şirul căutat are cel puţin un caracter;
• şirul cu care se înlocuieşte poate fi şirul vid (indicat prin linie goală în fişierul de intrare).

Exemplul 1

replace.in

3
esti
este
joi
vineri

_
azi esti joi si esti vesel

replace.out

azi_este_vineri_si_este_vesel

Explicație

Se aplică $3$ reguli:

• esti se înlocuieşte cu este
• joi se înlocuieşte cu vineri
• spaţiu se înlocuieşte cu underscore

Transformările succesive:

• azi esti joi si esti vesel devine azi este joi si este vesel (esti s-a înlocuit cu este)
• azi este joi si este vesel devine azi este vineri si este vesel (joi s-a înlocuit cu vineri)
• azi este vineri si este vesel devine azi_este_vineri_si_este_vesel (spaţiu s-a înlocuit cu underscore)