Problem F
Picky Byteasar
Just like every year, since spring Byteasar has been wondering what kind of chain he should decorate his house with for Christmas. So he pulls out his worn-out chain of $n$ lights. Each lamp has one of five available colors, which we will denote by letters from a to e. Byteasar has begun to modify the colors of the lamps.
The modification operation takes place in such a way that Byteasar selects two colors $a$ and $b$ and a positive integer integer $p$, and then he replaces the first $p$ lamps that have color $a$ with the lamps colored $b$.
Since Byteasar is planning a lot of changes, he has asked you to write a program that will print the appearance of the chain after $m$ modifications.
Input
The first line of the input contains two integers $n$ and $m$ ($1 \leq n, m \leq 1\, 000\, 000$), specifying the number of lamps in the chain and the number of operations. In the second line there is a sequence of $n$ lowercase letters of the English alphabet (without any spaces) denoting the colors of successive lamps in the chain.
The next $m$ lines contain descriptions of the color changes; the $i$-th of these lines contains one positive integer $p_ i$ and two different lowercase letters of the English alphabet $a_ i$ and $b_ i$, separated by single spaces. Such a line means that $p_ i$ of the first lamps of color $a_ i$ should be changed to lamps of color $b_ i$. You can assume that there are at least $p_ i$ of lamps of color $a_ i$ in the chain before the operation.
Output
Output a single line containing a string of $n$ letters from a to e (without any spaces) denoting the colors of successive lamps in the chain after all change operations.
Explanation of Sample
The colors of the lights changes as follows:
\[ \verb+acabbabbac+ \to \verb+acaccacbac+ \to \verb+bcbccbcbbc+ \to \verb+babaabcbbc+. \]Scoring
The tests are divided into the following subtasks. The tests for each subtask consist of one or more separate test groups.
Subtask |
Conditions |
Points |
1 |
$n \leq 100\, 000$, $m \leq 100$ |
17 |
2 |
$n, m \leq 100\, 000$ |
18 |
3 |
the chain always consists of only lights of color a or b |
29 |
4 |
the chain always consists of only lights of color a, b or c |
17 |
5 |
none |
19 |
Sample Input 1 | Sample Output 1 |
---|---|
10 3 acabbabbac 3 b c 4 a b 3 c a |
babaabcbbc |