Se dă un șir s = s0, s1,…, sn-1 de n litere mici. Prin s[i..j] se înțelege secvența si, si+1, …, sj. Asupra șirului se efectuează de mai multe ori operația switch(i,j,c1,c2), care în secvența s[i..j] modifică orice apariție a literei c1 în litera c2. De exemplu, dacă s=abcdaabcdaaab, atunci switch(0,5,'a','z') face ca șirul să devină s=zbcdzzbcdaaab.

Cerința

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 de intrare 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 c1 c2, reprezentând operația switch(i,j,c1,c2).

Date de ieșire

Fișierul de ieșire switchletters.out va 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 ≤ n ≤ 1.000.000.
• Șirul s nu conține alte caractere în afară de litere mici.
• Într-o operație switch(i,j,c1,c2), întotdeauna 0 ≤ i ≤ j < n, iar c1 ≠ c2.
• 1 ≤ m ≤ 217.

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

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