switchletters

Se dă un șir $s = s_0,s_1,...,s_{n-1}$ de $n$ litere mici. Prin $s[i..j]$ se înțelege secvența $s_i,s_{i+1},...,s_j$. Asupra șirului se efectuează de mai multe ori operația $switch(i, j, c_1, c_2)$, care în secvența $s[i..j]$ modifică orice apariție a literei $c_1$ în litera $c_2$. De exemplu, dacă $s=abcdaabcdaaab$, atunci $switch(0,5,'a','z')$ face ca șirul să devină $s=zbcdzzbcdaaab$.

Cerință

Dându-se șirul $s$ și $m$ operații switch, să se afișeze șirul $s$ după efectuarea celor $m$ operații.

Date de intrare

Fișierul switchletters.in conține pe prima linie șirul $s$, pe a doua linie numărul natural $m$, iar pe următoarele $m$ linii se află câte două numere naturale și două litere mici ale alfabetului englez, separate prin câte un spațiu $i \ j \ c_1 \ c_2$, reprezentând operația $switch(i,j,c_1,c_2)$.

Date de ieșire

Fișierul switchletters.out conține șirul $s$ după efectuarea celor $m$ operații.

Restricții și precizări

• Șirul $s$ conține cel mult $1 \ 000 \ 000$ litere mici: $1 \le n \le 1 \ 000 \ 000$.
• Șirul $s$ nu conține alte caractere în afară de litere mici.
• Într-o operație $switch(i, j, c_1, c_2)$, întotdeauna $0 \leq i \leq j < n$, iar $c_1 \neq c_2$.
• $1 \leq m \leq 2^{17}$.

Exemplul 1

switchletters.in

aaaabbbbcccc
3
0 2 a y
5 9 b c
1 3 a z

switchletters.out

yyyzbccccccc

Explicație

Pentru primul exemplu, După operația $switch(0,2,’a’,’y’)$, $s=yyyabbbbcccc$.
După operația $switch(5,9,’b’,’c’)$, $s=yyyabccccccc$.
După operația $switch(1,3,’a’,’z’)$, $s=yyyzbccccccc$

Exemplul 2

switchletters.in

anaaremere
2
3 6 z y
2 7 o x

switchletters.out

anaaremere

Explicație

Pentru al doilea exemplu, $s$ rămâne neschimbat, deoarece literele $z$ și $o$ nu apar în șir.