The war between the continent of Bezorath and the Earth Disaster Legion has reached a stalemate. The elves, who have lived on the continent of Bezorath for generations, have begun searching for artifacts left behind by the gods of ancient times, hoping to use their mysterious power to help them defeat the Earth Disaster Legion.

After paying a heavy price, the elves retrieved a well-preserved magic staff from the treacherous ancient battlefield. However, after the "War of Ragnarök," which is considered taboo in all history books, the arcane gems embedded in the staff were damaged, and its magical power was almost exhausted. The elven leadership decided at the Supreme Council to use the power of the entire nation to collect the remaining arcane gems and offered a huge reward to any skilled craftsman who could repair the staff.

As the 501st successor of the magic lineage, you have accepted this arduous and sacred mission. The staff has $n$ arcane gems embedded from left to right. There are 10 types of arcane gems, represented by the digits 0123456789. Some positions are damaged, represented by ., and you need to fill in each damaged part with a valid arcane gem (there is no limit to the number of each type of arcane gem, and you cannot replace the undamaged gems). The ancient magic book records $m$ types of spells $(S_i, V_i)$, where $S_i$ is a non-empty digit string and $V_i$ is the magical power stimulated by this combination.

The initial magical power of the staff is $\mathrm{Magic} = 1$. Whenever a continuous segment of gems in the staff is equal to $S_i$, the magical power $\mathrm{Magic}$ is multiplied by $V_i$. However, if the staff contains too many spells, it is no longer pure, causing the magical power to decrease: let $c$ be the number of spells contained in the staff (if the spell category is the same but the position is different, it is counted multiple times), the final magical power of the staff is $\sqrt[c]{\mathrm{Magic}}$. (If $c = 0$, the final magical power of the staff is $1$.)

For example, if there are two spells $(01, 3)$ and $(10, 4)$, the magical power of the staff 0101 is $\sqrt[3]{3 \times 4 \times 3}$.

You need to maximize the final magical power of the repaired staff and output any one solution.

Input

The first line contains two positive integers $n$ and $m$, representing the number of gems and the number of spells.

The second line contains a string $T$ of length $n$, representing the initial staff.

The next $m$ lines each contain a non-empty digit string $S_i$ and a positive integer $V_i$, representing each type of spell.

Output

Output the gems embedded on the final staff from left to right. If there are multiple solutions, any one of them will suffice.

Examples

Input 1

4 3
....
1 2
2 2
3 1

Output 1

2019

Note 1

The final magical power of the staff is $2$.

Input 2

5 4
..0..
0 2
00 2
01 4
10 3

Output 2

11012

Note 2

The final magical power of the staff is $\sqrt[3]{2 \times 3 \times 4}$.

Input 3

18 6
...2.1.0.1..1.0..1
011 6
111 4
010 12
121 7
101 5
10 3

Output 3

121211203112120121

Subtasks

Let $s = \sum_{i=1}^{m} |S_i|$, which is the sum of the lengths of all spell strings.

For $100\%$ of the data, $1\le n, m, s \le 1501$ and $1\le V_i\le 10^9$.