Problem Description

The war between the Bezorath continent and the invading Earth Disaster Army has reached a stalemate. The elves, who have lived on the Bezorath continent for generations, are seeking ancient artifacts left behind by the gods in an attempt to harness the mysterious power of these relics to defeat the Earth Disaster Army.

After suffering significant losses, the elves retrieved a well-preserved staff from the perilous ancient battlefield. However, after the infamous "Twilight of the Gods" battle, the arcane gems embedded in the staff are damaged, and its divine power is nearly depleted. The elven高层 decided in a supreme council meeting to gather all remaining arcane gems in the nation and offer a substantial reward to any skilled craftsmen capable of repairing the staff.

As the 501st successor of the divine arts, you have accepted this arduous and sacred mission.

The staff is embedded with \( n \) arcane gems from left to right, with a total of 10 types of gems, represented by the digits "0123456789". Some positions have damaged gems, represented by ".", and you need to replace these with intact gems (with an unlimited supply of each type, but without replacing undamaged gems). Ancient magical texts record \( m \) spells \((S_i, V_i)\), where \( S_i \) is a non-empty numeric string and \( V_i \) is the divine power that this combination can activate.

The initial divine power value of the staff, \( Magic \), is 1. Whenever a continuous sequence of gems on the staff matches \( S_i \), the divine power value \( Magic \) is multiplied by \( V_i \). However, if the staff contains too many spells, its purity is compromised, reducing its divine power: let \( c \) be the number of spells the staff contains (spells of the same type appearing in different positions are counted multiple times), the final divine power value of the staff is \( \sqrt[c]{Magic} \) (if \( c = 0 \), the final divine power value is 1).

For example, with two spells \((01, 3)\) and \((10, 4)\), the divine power value of the staff "0101" is \( \sqrt[3]{3 \times 4 \times 3} \).

You need to maximize the final divine power value of the repaired staff and output any valid solution.

Input Format

The first line contains two positive integers \( n \) and \( m \), representing the number of gems and the number of spells, respectively.

The second line is a string \( T \) of length \( n \), representing the initial state of the staff.

The next \( m \) lines each contain a non-empty numeric string \( S_i \) and a positive integer \( V_i \), representing each spell.

Output Format

Output the sequence of gems embedded in the staff from left to right after repair, with any valid solution accepted.

Sample Input and Output

Input Sample #1

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

Output Sample #1

2019

Input Sample #2

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

Output Sample #2

11012

Input Sample #3

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

Output Sample #3

121211203112120121

Notes

Sample 1: The final divine power value of the staff is 2.

Sample 2: The final divine power value of the staff is \( \sqrt[3]{2 \times 3 \times 4} \).

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

见题面 Input 部分

见题面 Output 部分