Just like every year, since spring, Bytasar has been wondering what kind of chain he should use to decorate his house for Christmas. He has pulled out his worn-out chain of $n$ lamps. Each lamp has one of five available colors, which we will denote with letters from a to e. Bytasar has started modifying the colors of individual lamps.

A modification operation consists of Bytasar choosing two colors $a$ and $b$ and a positive integer $p$, and then changing the first $p$ lamps from the left that have color $a$ to color $b$.

Since Bytasar is planning many changes, he has asked you to write a program that will present the appearance of the chain after $m$ modifications.

Input

The first line of input contains two integers $n$ and $m$ ($1 \le n, m \le 1\,000\,000$), representing the number of lamps in the chain and the number of color change operations. The second line contains a string of $n$ lowercase English letters (without any spaces) representing the colors of the consecutive 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 distinct lowercase English letters $a_i$ and $b_i$, separated by single spaces. Such a line means that the first $p_i$ lamps of color $a_i$ should be changed to lamps of color $b_i$. You may assume that before the operation, there are at least $p_i$ lamps of color $a_i$ in the chain.

Output

Output one line containing a string of $n$ letters from a to e (without any spaces) representing the colors of the consecutive lamps in the chain after all change operations.

Examples

Input 1

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

Output 1

babaabcbbc

Note 1

The colors of the lamps changed in the following way: acabbabbac $\to$ acaccacbac $\to$ bcbccbcbbc $\to$ babaabcbbc.

Evaluation

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

Evaluation Tests

• Test 1: $n = 1000, m = 1000$, the chain is $ababab\dots ab$, consecutive operations alternately change the first 250 lamps of color a to color b, and then the first 250 lamps of color b to color a;
• Test 2: $n = 90\,000, m = 100\,000$, the initial chain is $aaa\dots abbb\dots bccc\dots c$ (30\,000 lamps of the same color in a row), consecutive operations cyclically change the first 10\,000 lamps of color a to color b, the first 10\,000 lamps of color a to color c, the first 10\,000 lamps of color b to color a, the first 10\,000 lamps of color c to color a;
• Test 3: $n = 1\,000\,000, m = 1\,000\,000$, the initial chain is $abcde$ repeated 200\,000 times, consecutive operations change an increasing number of initial lamps in the cycle of colors $a \to b \to c \to d \to e \to a$.