Bezorath 大陸抵抗地災軍團入侵的戰爭進入了僵持的階段，世世代代生活在 Bezorath 這片大陸的精靈們開始尋找遠古時代諸神遺留的神器，試圖藉助神器的神祕力量幫助她們戰勝地災軍團。

在付出了慘痛的代價後，精靈們從步步凶險的遠古戰場取回了一件保存尚完好的神杖。但在經歷過那場所有史書都視為禁忌的「諸神黃昏之戰」後，神杖上鑲嵌的奧術寶石已經殘缺，神力也幾乎消耗殆盡。精靈高層在至高會議中決定以舉國之力收集殘存至今的奧術寶石，並重金懸賞天下能工巧匠修復這件神杖。

你作為神術一脈第五百零一位傳人，接受了這個艱鉅而神聖的使命。神杖上從左到右鑲嵌了 $n$ 顆奧術寶石，奧術寶石一共有 $10$ 種，用數字 0123456789 表示。有些位置的寶石已經殘缺，用 . 表示，你需要用完好的奧術寶石填補每一處殘缺的部分（每種奧術寶石個數不限，且不能夠更換未殘缺的寶石）。古老的魔法書上記載了 $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$。）

例如有兩種咒語 $(01, 3)$ 、$(10, 4)$，那麼神杖 0101 的神力值為 $\sqrt[3]{ 3 \times 4 \times 3}$。

你需要使修復好的神杖的最終的神力值最大，輸出任何一個解即可。

輸入格式

第一行兩個正整數 $n, m$，表示寶石數和咒語數。

第二行為一個長度為 $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|$，即所有咒語的串長之和。

對於 $100\%$ 的資料，滿足 $1\le n, m, s \le 1501, 1\le V_i\le 10^9$。