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:

Scoring

The tests are divided into the following subtasks. The tests for each subtask consist of one or more separate test groups.

10 3
acabbabbac
3 b c
4 a b
3 c a

babaabcbbc