У Пети есть строка длины n, состоящая из прописных и строчных букв латинского алфавита, а также из цифр.
Он выполняет со своей строкой по очереди m операций. Каждая операция описывается двумя целыми числами l и r и одним символом c — Петя удаляет из своей строки все символы c, находящиеся между позициями l и r, включительно. Очевидно, что после каждой операции длина строки либо не изменяется, либо уменьшается.
Определите как будет выглядеть строка Пети после выполнения m операций.
Выходные данные
Выведите строку Пети после выполнения всех m операций. Если после выполнения всех операций строка Пети станет пустой, выведите пустую строку.
Примечание
В первом примере после выполнения первой операции из строки удалятся обе буквы «a», и строка примет вид «bc». После выполнения второй операции из строки удалится буква «c» (стоящая на второй позиции), и строка примет вид «b».
Во втором примере после выполнения первой операции из строки удаляется «0», находящийся во второй позиции. После этого строка примет вид «Az». После выполнения второй операции строка не изменится.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
abac
1 3 a
2 2 c
|
b
|
|
2
|
3 2
A0z
1 3 0
1 1 z
|
Az
|
|
3
|
10 4
agtFrgF4aF
2 5 g
4 9 F
1 5 4
1 7 a
|
tFrg4
|
|
4
|
9 5
aAAaBBccD
1 4 a
5 6 c
2 3 B
4 4 D
2 3 A
|
AB
|