Wojna kontynentu Bezorath z inwazją armii kataklizmów weszła w fazę impasu. Elfy, zamieszkujące te ziemie od pokoleń, zaczęły poszukiwać artefaktów pozostawionych przez starożytnych bogów, próbując wykorzystać ich tajemniczą moc do pokonania najeźdźców.
Po poniesieniu ogromnych strat, elfy odzyskały z niebezpiecznego starożytnego pola bitwy wciąż zachowaną w całości laskę. Jednak po „Wojnie Zmierzchu Bogów”, uważanej w kronikach za temat tabu, osadzone na lasce magiczne klejnoty uległy zniszczeniu, a jej moc niemal całkowicie wygasła. Wysoka Rada Elfów zdecydowała, że przy użyciu zasobów całego kraju zgromadzi pozostałe klejnoty i wyznaczy wysoką nagrodę dla rzemieślnika, który naprawi ten artefakt.
Jako pięćset pierwszy potomek rodu magów, przyjąłeś to trudne i święte zadanie. Na lasce od lewej do prawej osadzonych jest $n$ klejnotów. Istnieje $10$ rodzajów klejnotów, oznaczonych cyframi 0123456789. Niektóre miejsca są puste, co oznaczono symbolem .. Musisz wypełnić każde puste miejsce dostępnymi klejnotami (liczba klejnotów każdego rodzaju jest nieograniczona, nie można wymieniać już istniejących klejnotów). Starożytna księga magii zawiera $m$ rodzajów zaklęć $(S_i, V_i)$, gdzie $S_i$ jest niepustym ciągiem cyfr, a $V_i$ to moc wyzwalana przez taką kombinację.
Początkowa wartość mocy laski wynosi $\mathrm{Magic} = 1$. Za każdym razem, gdy na lasce pojawi się ciąg klejnotów równy $S_i$, wartość $\mathrm{Magic}$ zostaje pomnożona przez $V_i$. Jeśli jednak laska zawiera zbyt wiele zaklęć, traci swoją czystość, co obniża jej moc: niech $c$ oznacza liczbę zaklęć zawartych w lasce (jeśli zaklęcia są tego samego typu, ale występują w różnych miejscach, każde wystąpienie liczy się osobno). Ostateczna moc laski wynosi $\sqrt[c]{\mathrm{Magic}}$. (Jeśli $c = 0$, ostateczna moc laski wynosi $1$).
Na przykład, jeśli istnieją dwa zaklęcia $(01, 3)$ oraz $(10, 4)$, to moc laski 0101 wynosi $\sqrt[3]{3 \times 4 \times 3}$.
Twoim zadaniem jest zmaksymalizowanie ostatecznej mocy naprawionej laski. Wystarczy wypisać dowolne poprawne rozwiązanie.
Wejście
Pierwsza linia zawiera dwie liczby całkowite $n, m$, oznaczające liczbę klejnotów oraz liczbę zaklęć.
Druga linia zawiera ciąg $T$ o długości $n$, reprezentujący początkowy stan laski.
Następnie $m$ linii zawiera niepusty ciąg cyfr $S_i$ oraz liczbę całkowitą $V_i$, opisujące każde zaklęcie.
Wyjście
Wypisz stan klejnotów na naprawionej lasce od lewej do prawej. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.
Przykład
Wejście 1
4 3 .... 1 2 2 2 3 1
Wyjście 1
2019
Uwagi
Ostateczna moc laski wynosi $2$.
Wejście 2
5 4 ..0.. 0 2 00 2 01 4 10 3
Wyjście 2
11012
Uwagi
Ostateczna moc laski wynosi $\sqrt[3]{2 \times 3 \times 4}$.
Wejście 3
18 6 ...2.1.0.1..1.0..1 011 6 111 4 010 12 121 7 101 5 10 3
Wyjście 3
121211203112120121
Podzadania
Niech $s = \sum_{i=1}^{m} |S_i|$, czyli suma długości wszystkich ciągów zaklęć.
| Test | $n\le$ | $s\le$ | Właściwości specjalne |
|---|---|---|---|
| $1\sim 3$ | $6$ | $20$ | |
| $4\sim 5$ | $501$ | $5$ | |
| $6$ | $501$ | $501$ | Wszystkie $V_i$ są takie same |
| $7$ | $501$ | $501$ | $V_i$ przyjmuje co najwyżej $2$ różne wartości |
| $8$ | $501$ | $501$ | $V_i$ przyjmuje co najwyżej $3$ różne wartości |
| $9\sim 11$ | $501$ | $501$ | $T$ składa się wyłącznie z . |
| $12\sim 13$ | $501$ | $501$ | $T$ ma co najwyżej $3$ miejsca z . |
| $14\sim 16$ | $501$ | $501$ | |
| $17\sim 20$ | $1501$ | $1501$ |
Dla $100\%$ danych wejściowych spełnione są warunki: $1\le n, m, s \le 1501, 1\le V_i\le 10^9$.