Cuộc chiến của lục địa Bezorath chống lại sự xâm lược của quân đoàn thảm họa đã rơi vào thế bế tắc. Những người tiên tộc, vốn sinh sống qua bao thế hệ trên mảnh đất Bezorath, bắt đầu tìm kiếm các cổ vật do chư thần để lại từ thời viễn cổ, với hy vọng mượn sức mạnh huyền bí của chúng để đánh bại quân đoàn thảm họa.

Sau khi phải trả giá bằng những mất mát đau thương, người tiên tộc đã thu hồi được một cây thần trượng vẫn còn nguyên vẹn từ chiến trường cổ đại đầy rẫy hiểm nguy. Tuy nhiên, sau "Trận chiến hoàng hôn của chư thần" – sự kiện mà mọi sử sách đều coi là cấm kỵ, các viên ngọc huyền thuật khảm trên thần trượng đã bị hư hại và sức mạnh thần thánh gần như đã cạn kiệt. Hội đồng tối cao của người tiên tộc quyết định huy động toàn lực quốc gia để thu thập những viên ngọc huyền thuật còn sót lại, đồng thời treo thưởng hậu hĩnh cho những nghệ nhân tài ba có thể khôi phục cây thần trượng này.

Với tư cách là truyền nhân thứ 501 của dòng dõi thần thuật, bạn đã chấp nhận sứ mệnh gian nan và thiêng liêng này. Trên thần trượng có khảm $n$ viên ngọc huyền thuật từ trái sang phải, có tất cả $10$ loại ngọc, được biểu diễn bằng các chữ số 0123456789. Một số vị trí đã bị mất ngọc, được ký hiệu bằng dấu ., bạn cần dùng các viên ngọc huyền thuật còn nguyên vẹn để lấp đầy mọi chỗ trống (số lượng mỗi loại ngọc là không giới hạn, và không được phép thay thế những viên ngọc chưa bị mất). Trong cuốn ma pháp thư cổ ghi lại $m$ loại thần chú $(S_i, V_i)$, trong đó $S_i$ là một chuỗi số không rỗng, và $V_i$ là sức mạnh thần thánh mà tổ hợp này có thể kích hoạt.

Giá trị sức mạnh thần thánh ban đầu của thần trượng là $\mathrm{Magic} = 1$. Mỗi khi một đoạn liên tiếp các viên ngọc trên thần trượng khớp với $S_i$, giá trị $\mathrm{Magic}$ sẽ được nhân với $V_i$. Tuy nhiên, nếu thần trượng chứa quá nhiều thần chú thì nó sẽ không còn thuần khiết, dẫn đến sức mạnh bị suy giảm: giả sử $c$ là tổng số thần chú mà thần trượng chứa (nếu các loại thần chú giống nhau nhưng xuất hiện ở vị trí khác nhau thì vẫn tính là nhiều lần), giá trị sức mạnh cuối cùng của thần trượng là $\sqrt[c]{\mathrm{Magic}}$. (Nếu $c = 0$ thì giá trị sức mạnh cuối cùng là $1$).

Ví dụ, nếu có hai loại thần chú $(01, 3)$ và $(10, 4)$, thì thần trượng 0101 sẽ có giá trị sức mạnh là $\sqrt[3]{3 \times 4 \times 3}$.

Bạn cần làm cho giá trị sức mạnh cuối cùng của thần trượng sau khi sửa chữa đạt mức lớn nhất. Hãy xuất ra bất kỳ một lời giải nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên dương $n, m$, lần lượt là số lượng viên ngọc và số lượng thần chú.

Dòng thứ hai chứa một chuỗi $T$ có độ dài $n$, biểu diễn thần trượng ban đầu.

$m$ dòng tiếp theo, mỗi dòng chứa một chuỗi số không rỗng $S_i$ và một số nguyên dương $V_i$, biểu diễn mỗi loại thần chú.

Dữ liệu ra

Xuất ra chuỗi các viên ngọc được khảm trên thần trượng từ trái sang phải sau khi hoàn thiện. Nếu có nhiều lời giải, hãy xuất ra bất kỳ lời giải nào.

Ví dụ

Ví dụ 1

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

Ví dụ 1

2019

Ghi chú 1

Giá trị sức mạnh cuối cùng của thần trượng là $2$.

Ví dụ 2

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

Ví dụ 2

11012

Ghi chú 2

Giá trị sức mạnh cuối cùng của thần trượng là $\sqrt[3]{2 \times 3 \times 4}$.

Ví dụ 3

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

Ví dụ 3

121211203112120121

Nhiệm vụ con

Đặt $s = \sum_{i=1}^{m} |S_i|$, là tổng độ dài của tất cả các chuỗi thần chú.

Với $100\%$ dữ liệu, thỏa mãn $1\le n, m, s \le 1501, 1\le V_i\le 10^9$.