{"problem":{"name":"F. Letters Removing","description":{"content":"Petya has a string of length _n_ consisting of small and large English letters and digits. He performs _m_ operations. Each operation is described with two integers _l_ and _r_ and a character _c_: P","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF899F"},"statements":[{"statement_type":"Markdown","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.\n\n## Input\n\nThe 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.\n\n## Output\n\nPrint the string Petya will obtain after performing all _m_ operations. If the strings becomes empty after all operations, print an empty line.\n\n[samples]\n\n## Note\n\nIn 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.","is_translate":false,"language":"English"},{"statement_type":"Markdown","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## Input\n\n第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 2·10^5$）——字符串的长度和操作次数。第二行包含一个长度为 $n$ 的字符串，由小写和大写英文字母及数字组成。字符串中的位置从 $1$ 开始编号。接下来的 $m$ 行中，每行包含两个整数 $l$ 和 $r$（$1 ≤ l ≤ r$），后跟一个字符 $c$，该字符为小写或大写英文字母或数字。此行描述一次操作。保证在当前操作前，$r$ 不超过字符串 $s$ 的长度。\n\n## Output\n\n请输出 Petya 执行所有 $m$ 次操作后得到的字符串。如果所有操作后字符串变为空，请输出一个空行。\n\n[samples]\n\n## Note\n\n在第一个例子中，第一次操作移除了两个字母 '_a_'，因此字符串变为 \"_bc_\"。第二次操作移除了第二个位置上的字母 '_c_'，字符串变为 \"_b_\"。在第二个例子中，第一次操作移除了第二个位置上的 '_0_'，之后字符串变为 \"_Az_\"。第二次操作中字符串没有变化。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**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)} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF899F","tags":["data structures","strings"],"sample_group":[["4 2\nabac\n1 3 a\n2 2 c","b"],["3 2\nA0z\n1 3 0\n1 1 z","Az"],["10 4\nagtFrgF4aF\n2 5 g\n4 9 F\n1 5 4\n1 7 a","tFrg4"],["9 5\naAAaBBccD\n1 4 a\n5 6 c\n2 3 B\n4 4 D\n2 3 A","AB"]],"created_at":"2026-03-03 11:00:39"}}