E. Массовые замены
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Поликарпа есть строка s из n строчных латинских символов. Над строкой он последовательно проводит m операций. Каждая операция i заменяет все символы fri на toi на позициях li... ri.

Поликарп устал проводить замены вручную и спрашивает вас, как будет выглядеть строка после проведения всех операций.

Входные данные

В первой строке записано число n, 1 ≤ n ≤ 100000 — длина строки. Во второй строке записана строка s. В третьей записано число m, 0 ≤ m ≤ 100000 — количество операций. В следующих m строках записаны операции.

Каждая операция имеет вид строки li ri fri toi, где i — номер операции. 1 ≤ li ≤ ri ≤ n — на каком интервале производить замену. fri и toi — это строчные латинские символы, определяющие, какой символ на что заменить. Все разделяется пробелами.

Выходные данные

В единственной строке вывести, что получится в результате замен символов.

Примеры
Входные данные
5
aaaaa
4
1 5 a b
2 4 b c
3 3 c a
1 5 a e
Выходные данные
bcecb
Входные данные
7
abadaba
4
1 3 a c
4 7 a a
1 7 b a
1 7 a z
Выходные данные
czcdzzz