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$입니다.)

예를 들어 두 가지 주문 $(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|$를 모든 주문 문자열 길이의 합이라고 합시다.

모든 데이터는 $1\le n, m, s \le 1501, 1\le V_i\le 10^9$를 만족합니다.