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