F. Letters Removing

Codeforces

IDCF899F

Time2000ms

Memory256MB

Difficulty—

data structuresstrings

English · Original

Chinese · Translation

Formal · Original

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_: 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. Find how the string will look like after Petya performs all _m_ operations. ## Input The first string contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 2·105) — the length of the string and the number of operations. The 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. Each 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. ## Output Print the string Petya will obtain after performing all _m_ operations. If the strings becomes empty after all operations, print an empty line. [samples] ## Note 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_". In 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.

Petya 有一个由小写和大写英文字母及数字组成的长度为 $n$ 的字符串。他执行 $m$ 次操作。每次操作由两个整数 $l$ 和 $r$ 以及一个字符 $c$ 描述：Petya 会从字符串中移除所有位于位置 $l$ 到 $r$（包含两端）之间的字符 $c$。显然，每次操作后字符串的长度保持不变或减少。请找出 Petya 执行所有 $m$ 次操作后字符串的样子。第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 2·10^5$）——字符串的长度和操作次数。第二行包含一个长度为 $n$ 的字符串，由小写和大写英文字母及数字组成。字符串中的位置从 $1$ 开始编号。接下来的 $m$ 行中，每行包含两个整数 $l$ 和 $r$（$1 ≤ l ≤ r$），后跟一个字符 $c$，该字符为小写或大写英文字母或数字。此行描述一次操作。保证在当前操作前，$r$ 不超过字符串 $s$ 的长度。请输出 Petya 执行所有 $m$ 次操作后得到的字符串。如果所有操作后字符串变为空，请输出一个空行。在第一个例子中，第一次操作移除了两个字母 '_a_'，因此字符串变为 "_bc_"。第二次操作移除了第二个位置上的字母 '_c_'，字符串变为 "_b_"。在第二个例子中，第一次操作移除了第二个位置上的 '_0_'，之后字符串变为 "_Az_"。第二次操作中字符串没有变化。 ## Input 第一行包含两个整数 $n$ 和 $m$（$1 ≤ n, m ≤ 2·10^5$）——字符串的长度和操作次数。第二行包含一个长度为 $n$ 的字符串，由小写和大写英文字母及数字组成。字符串中的位置从 $1$ 开始编号。接下来的 $m$ 行中，每行包含两个整数 $l$ 和 $r$（$1 ≤ l ≤ r$），后跟一个字符 $c$，该字符为小写或大写英文字母或数字。此行描述一次操作。保证在当前操作前，$r$ 不超过字符串 $s$ 的长度。 ## Output 请输出 Petya 执行所有 $m$ 次操作后得到的字符串。如果所有操作后字符串变为空，请输出一个空行。 [samples] ## Note 在第一个例子中，第一次操作移除了两个字母 '_a_'，因此字符串变为 "_bc_"。第二次操作移除了第二个位置上的字母 '_c_'，字符串变为 "_b_"。在第二个例子中，第一次操作移除了第二个位置上的 '_0_'，之后字符串变为 "_Az_"。第二次操作中字符串没有变化。

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 2 \cdot 10^5 $. Let $ s \in \Sigma^n $ be the initial string, where $ \Sigma $ is the set of English letters (uppercase and lowercase) and digits. Let $ 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 $. **Constraints** 1. $ 1 \leq n, m \leq 2 \cdot 10^5 $ 2. 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. 3. Each $ c_i \in \Sigma $. **Objective** Apply 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)} $. Output the final string $ s^{(m)} $.

Samples

Input #1

4 2
abac
1 3 a
2 2 c

Output #1

Input #2

Output #2

Az

Input #3

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

Output #3

tFrg4

Input #4

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

Output #4

AB

API Response (JSON)

{
  "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_: P...",
      "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...",
      "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 lo...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments