{"raw_statement":[{"iden":"statement","content":"Petya has a string of length _n_ consisting of small and large English letters and digits.\n\nHe performs _m_ operations. Each operation is described with two integers _l_ and _r_ and a character _c_: Petya removes from the string all characters _c_ on positions between _l_ and _r_, inclusive. It's obvious that the length of the string remains the same or decreases after each operation.\n\nFind how the string will look like after Petya performs all _m_ operations."},{"iden":"input","content":"The first string contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 2·105) — the length of the string and the number of operations.\n\nThe second line contains the string of length _n_, consisting of small and large English letters and digits. Positions in the string are enumerated from 1.\n\nEach of the next _m_ lines contains two integers _l_ and _r_ (1 ≤ _l_ ≤ _r_), followed by a character _c_, which is a small or large English letter or a digit. This line describes one operation. It is guaranteed that _r_ doesn't exceed the length of the string _s_ before current operation."},{"iden":"output","content":"Print the string Petya will obtain after performing all _m_ operations. If the strings becomes empty after all operations, print an empty line."},{"iden":"examples","content":"Input\n\n4 2\nabac\n1 3 a\n2 2 c\n\nOutput\n\nb\n\nInput\n\n3 2\nA0z\n1 3 0\n1 1 z\n\nOutput\n\nAz\n\nInput\n\n10 4\nagtFrgF4aF\n2 5 g\n4 9 F\n1 5 4\n1 7 a\n\nOutput\n\ntFrg4\n\nInput\n\n9 5\naAAaBBccD\n1 4 a\n5 6 c\n2 3 B\n4 4 D\n2 3 A\n\nOutput\n\nAB"},{"iden":"note","content":"In the first example during the first operation both letters '_a_' are removed, so the string becomes \"_bc_\". During the second operation the letter '_c_' (on the second position) is removed, and the string becomes \"_b_\".\n\nIn the second example during the first operation Petya removes '_0_' from the second position. After that the string becomes \"_Az_\". During the second operations the string doesn't change."}],"translated_statement":[{"iden":"statement","content":"Petya 有一个由小写和大写英文字母及数字组成的长度为 $n$ 的字符串。\n\n他执行 $m$ 次操作。每次操作由两个整数 $l$ 和 $r$ 以及一个字符 $c$ 描述：Petya 会从字符串中移除所有位于位置 $l$ 到 $r$（包含两端）之间的字符 $c$。显然，每次操作后字符串的长度保持不变或减少。\n\n请找出 Petya 执行所有 $m$ 次操作后字符串的样子。\n\n第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 2·10^5$）——字符串的长度和操作次数。\n\n第二行包含一个长度为 $n$ 的字符串，由小写和大写英文字母及数字组成。字符串中的位置从 $1$ 开始编号。\n\n接下来的 $m$ 行中，每行包含两个整数 $l$ 和 $r$（$1 ≤ l ≤ r$），后跟一个字符 $c$，该字符为小写或大写英文字母或数字。此行描述一次操作。保证在当前操作前，$r$ 不超过字符串 $s$ 的长度。\n\n请输出 Petya 执行所有 $m$ 次操作后得到的字符串。如果所有操作后字符串变为空，请输出一个空行。\n\n在第一个例子中，第一次操作移除了两个字母 '_a_'，因此字符串变为 \"_bc_\"。第二次操作移除了第二个位置上的字母 '_c_'，字符串变为 \"_b_\"。\n\n在第二个例子中，第一次操作移除了第二个位置上的 '_0_'，之后字符串变为 \"_Az_\"。第二次操作中字符串没有变化。\n\n"},{"iden":"input","content":"第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 2·10^5$）——字符串的长度和操作次数。第二行包含一个长度为 $n$ 的字符串，由小写和大写英文字母及数字组成。字符串中的位置从 $1$ 开始编号。接下来的 $m$ 行中，每行包含两个整数 $l$ 和 $r$（$1 ≤ l ≤ r$），后跟一个字符 $c$，该字符为小写或大写英文字母或数字。此行描述一次操作。保证在当前操作前，$r$ 不超过字符串 $s$ 的长度。"},{"iden":"output","content":"请输出 Petya 执行所有 $m$ 次操作后得到的字符串。如果所有操作后字符串变为空，请输出一个空行。"},{"iden":"examples","content":"输入\n4 2\nabac\n1 3 a\n2 2 c\n输出\nb\n\n输入\n3 2\nA0z\n1 3 0\n1 1 z\n输出\nAz\n\n输入\n10 4\nagtFrgF4aF\n2 5 g\n4 9 F\n1 5 4\n1 7 a\n输出\ntFrg4\n\n输入\n9 5\naAAaBBccD\n1 4 a\n5 6 c\n2 3 B\n4 4 D\n2 3 A\n输出\nAB"},{"iden":"note","content":"在第一个例子中，第一次操作移除了两个字母 '_a_'，因此字符串变为 \"_bc_\"。第二次操作移除了第二个位置上的字母 '_c_'，字符串变为 \"_b_\"。在第二个例子中，第一次操作移除了第二个位置上的 '_0_'，之后字符串变为 \"_Az_\"。第二次操作中字符串没有变化。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 2 \\cdot 10^5 $.  \nLet $ s \\in \\Sigma^n $ be the initial string, where $ \\Sigma $ is the set of English letters (uppercase and lowercase) and digits.  \nLet $ O = \\{(l_i, r_i, c_i) \\mid i \\in \\{1, \\dots, m\\}\\} $ be the sequence of operations, where $ l_i, r_i \\in \\mathbb{Z}^+ $, $ l_i \\leq r_i $, and $ c_i \\in \\Sigma $.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 2 \\cdot 10^5 $  \n2. For each operation $ i $: $ 1 \\leq l_i \\leq r_i \\leq |s^{(i-1)}| $, where $ s^{(i-1)} $ is the string before the $ i $-th operation.  \n3. Each $ c_i \\in \\Sigma $.\n\n**Objective**  \nApply operations sequentially: for each operation $ i $, remove all occurrences of character $ c_i $ from positions $ l_i $ to $ r_i $ (inclusive) in the current string $ s^{(i-1)} $, producing $ s^{(i)} $.  \nOutput the final string $ s^{(m)} $.","simple_statement":null,"has_page_source":false}