Bezorath大陸における地災軍団の侵攻に対する抵抗戦争は膠着状態に陥り、Bezorathの地に代々住まうエルフたちは、地災軍団を打ち破る力を求めて、古代の神々が遺した神器を探し始めました。

多大な犠牲を払った末、エルフたちは危険極まりない古代の戦場から、かろうじて原型を留めた神杖を回収しました。しかし、あらゆる歴史書で禁忌とされる「神々の黄昏（ラグナロク）」の戦いを経て、神杖に埋め込まれていた奥術宝石は欠け落ち、神力もほとんど枯渇していました。エルフの上層部は至高会議において、国を挙げて残存する奥術宝石を収集し、多額の懸賞金を懸けてこの神杖を修復できる名工を募ることを決定しました。

あなたは神術の継承者として501番目に名を連ねる者として、この困難かつ神聖な使命を受け入れました。神杖には左から右へ $n$ 個の奥術宝石が埋め込まれており、奥術宝石は 0123456789 で表される10種類が存在します。一部の場所の宝石は欠けており . で表されています。あなたは、欠けているすべての部分を適切な奥術宝石で埋める必要があります（各種類の奥術宝石の個数に制限はなく、欠けていない宝石を交換することはできません）。古の魔法書には $m$ 種類の呪文 $(S_i, V_i)$ が記されており、$S_i$ は空ではない数字の列、$V_i$ はその組み合わせによって引き出される神力を表します。

神杖の初期神力値は $\mathrm{Magic} = 1$ です。神杖の中に $S_i$ と一致する連続した宝石の列が現れるたびに、神力値 $\mathrm{Magic}$ は $V_i$ 倍されます。しかし、神杖に含まれる呪文が多すぎると純粋さが失われ、神力が低下します。$c$ を神杖に含まれる呪文の総数（呪文の種類が同じでも出現位置が異なれば別々に数える）とすると、神杖の最終的な神力値は $\sqrt[c]{\mathrm{Magic}}$ となります。（$c = 0$ の場合、最終的な神力値は $1$ とします。）

例えば、2種類の呪文 $(01, 3)$ と $(10, 4)$ がある場合、神杖 0101 の神力値は $\sqrt[3]{3 \times 4 \times 3}$ となります。

修復後の神杖の最終的な神力値を最大化してください。解が複数ある場合は、そのうちのいずれかを出力してください。

入力

1行目に2つの正整数 $n, m$ が与えられ、それぞれ宝石の数と呪文の数を表します。

2行目に長さ $n$ の文字列 $T$ が与えられ、初期の神杖の状態を表します。

続く $m$ 行の各行に、空ではない数字の列 $S_i$ と正整数 $V_i$ が与えられ、各呪文を表します。

出力

最終的な神杖に埋め込まれた宝石を左から右へ順に出力してください。解が複数ある場合は、そのうちのいずれかを出力してください。

入出力例

入力 1

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

出力 1

2019

注記 1

杖の最終神力値は $2$ です。

入力 2

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

出力 2

11012

注記 2

杖の最終神力値は $\sqrt[3]{2 \times 3 \times 4}$ です。

入力 3

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

出力 3

121211203112120121

小課題

$s = \sum_{i=1}^{m} |S_i|$ を、すべての呪文の文字列の長さの合計とします。

すべてのデータにおいて、$1\le n, m, s \le 1501, 1\le V_i\le 10^9$ を満たします。