← 返回题目列表

Codeforces · 899/F

F. 字母删除

中文机器翻译题面 查看原题

Petya 有一个长度为 n 的字符串,由大小写英文字母和数字组成。

他执行 m 项操作。每个操作都用两个整数 l 和 r 以及一个字符 c 来描述:Petya 从字符串中删除 l 和 r(含)之间位置上的所有字符 c。很明显,每次操作后字符串的长度保持不变或减少。

找出 Petya 执行所有 m 个操作后字符串的样子。

输入

第一个字符串包含两个整数 n 和 m (1 ≤ n, m ≤ 2·105) — 字符串的长度和操作次数。

第二行包含长度为n的字符串,由大小写英文字母和数字组成。字符串中的位置从 1 开始枚举。

接下来的 m 行每行包含两个整数 l 和 r (1 ≤ l ≤ r),后跟一个字符 c,它是一个小或大的英文字母或数字。这一行描述了一个操作。保证r不超过当前操作前字符串s的长度。

输出

打印 Petya 在执行所有 m 次操作后将获得的字符串。如果所有操作后字符串变空,则打印空行。

示例

输入 #1

4 2
abac
1 3 a
2 2 c

输出 #1

b

输入 #2

3 2
A0z
1 3 0
1 1 z

输出 #2

Az

输入 #3

10 4
agtFrgF4aF
2 5 g
4 9 F
1 5 4
1 7 a

输出 #3

tFrg4

输入#4

9 5
aAAaBBccD
1 4 a
5 6 c
2 3 B
4 4 D
2 3 A

输出#4

AB

注意

在第一个示例中,在第一个操作期间,两个字母“a”都被删除,因此字符串变为“bc”。在第二次操作期间,字母“c”(第二个位置上)被删除,字符串变为“b”。

在第二个示例中,在第一个操作期间,Petya 从第二个位置删除“0”。之后该字符串变为“Az”。在第二次操作期间,字符串不会更改。