Restoration of the Ancient Staff

After a brutal war against the invading forces of the "Disaster Legion", the ancient elven people of the continent Bezorath recovered a magical staff from the forbidden battlefield of the "Twilight of the Gods". Over generations, its embedded arcane gems have become partially damaged. Your task as the 501st inheritor of the ancient magical art is to restore the staff by replacing every missing arcane gem (denoted by a dot '.') with a functioning one. Each gem is represented by one of the 10 digits in the string "0123456789".

Moreover, the ancient tome reveals m spells given as pairs \( (S_i, V_i) \), where \( S_i \) is a non-empty string of digits and \( V_i \) is a positive integer representing the magical enhancement triggered by that spell. Every time a contiguous substring of the restored staff matches \( S_i \), the staff's magic is multiplied by \( V_i \). The staff’s initial magic is \( Magic=1 \). However, the accumulation of too many spells dilutes its purity: if the total number of spell activations is \( c \) (counting multiple occurrences even of the same spell), the final magic value is given by \[ \text{FinalMagic} = \begin{cases} \sqrt[c]{Magic} & \text{if } c > 0\\ 1 & \text{if } c=0 \end{cases} \] (in LaTeX format).

For example, if there are two spells \( (01,3) \) and \( (10,4) \) and the restored staff is "0101", then the spell "01" occurs at positions 1–2 and 3–4, and "10" occurs at positions 2–3. Thus \( Magic = 3 \times 4 \times 3 = 36 \) and \( c=3 \), so the final magic value is \( \sqrt[3]{36} \).

Your goal is to restore the staff in such a way that its final magic value is maximized. You are allowed to use an unlimited supply of each type of gem, but you cannot alter gems that are already intact (non-dot characters). If multiple solutions achieve the maximum value, output any one of them.

inputFormat

The input is given as follows:

n m
s
S_1 V_1
S_2 V_2
... 
S_m V_m

where:

• n: the length of the staff (number of arcane gems).
• m: the number of spells.
• s: a string of length n containing characters from '0'-'9' and '.' (a dot indicates a damaged gem that needs to be replaced).
• For each spell, S_i is a non-empty string of digits and V_i is the magic multiplier (a positive integer) activated when an exact contiguous substring match of S_i is found in the restored staff.

outputFormat

Output a single string representing the restored staff after replacing every missing gem. The answer should maximize the final magic value as described.

sample

4 2
01.1
01 3
10 4

0101