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”。在第二次操作期间,字符串不会更改。