La guerra de resistencia del continente de Bezorath contra la invasión de la Legión del Desastre ha entrado en un punto muerto. Los elfos, que han vivido en el continente de Bezorath durante generaciones, han comenzado a buscar artefactos dejados por los dioses de la antigüedad, intentando utilizar el poder místico de estos objetos para ayudarles a derrotar a la Legión del Desastre.
Tras pagar un precio terrible, los elfos recuperaron un báculo sagrado que aún se conservaba en buen estado del peligroso campo de batalla antiguo. Sin embargo, después de la "Guerra del Ragnarök", considerada un tabú en todos los libros de historia, las gemas arcanas incrustadas en el báculo estaban dañadas y su poder divino casi se había agotado. En el consejo supremo, los líderes elfos decidieron reunir todas las gemas arcanas restantes con el esfuerzo de toda la nación y ofrecer una gran recompensa a los artesanos capaces de reparar el báculo.
Como el quingentésimo primer heredero del linaje de las artes arcanas, has aceptado esta ardua y sagrada misión. El báculo tiene $n$ gemas arcanas incrustadas de izquierda a derecha. Existen $10$ tipos de gemas arcanas, representadas por los dígitos 0123456789. Algunas posiciones tienen gemas dañadas, representadas por ., y debes rellenar cada parte dañada con gemas arcanas en buen estado (la cantidad de cada tipo de gema es ilimitada, y no se pueden reemplazar las gemas que no están dañadas). El antiguo libro de magia registra $m$ tipos de hechizos $(S_i, V_i)$, donde $S_i$ es una cadena de dígitos no vacía y $V_i$ es el poder divino que esta combinación puede activar.
El valor de poder divino inicial del báculo es $\mathrm{Magic} = 1$. Cada vez que aparece una secuencia continua de gemas en el báculo que es igual a $S_i$, el valor de $\mathrm{Magic}$ se multiplica por $V_i$. Sin embargo, si el báculo contiene demasiados hechizos, ya no es puro y su poder divino disminuye: sea $c$ el número de hechizos contenidos en el báculo (si los hechizos son del mismo tipo pero aparecen en diferentes posiciones, se cuentan como múltiples veces), el valor final del poder divino del báculo es $\sqrt[c]{\mathrm{Magic}}$. (Si $c = 0$, el valor final del poder divino del báculo es $1$).
Por ejemplo, si hay dos hechizos $(01, 3)$ y $(10, 4)$, el poder divino del báculo 0101 es $\sqrt[3]{3 \times 4 \times 3}$.
Debes maximizar el valor final del poder divino del báculo reparado. Puedes imprimir cualquier solución válida.
Entrada
La primera línea contiene dos enteros positivos $n, m$, que representan el número de gemas y el número de hechizos.
La segunda línea contiene una cadena $T$ de longitud $n$, que representa el báculo inicial.
Las siguientes $m$ líneas contienen cada una una cadena de dígitos no vacía $S_i$ y un entero positivo $V_i$, que representan cada tipo de hechizo.
Salida
Imprime las gemas incrustadas en el báculo final de izquierda a derecha. Si hay múltiples soluciones, puedes imprimir cualquiera de ellas.
Ejemplos
Entrada 1
4 3 .... 1 2 2 2 3 1
Salida 1
2019
Nota 1
El valor final del poder divino del báculo es $2$.
Entrada 2
5 4 ..0.. 0 2 00 2 01 4 10 3
Salida 2
11012
Nota 2
El valor final del poder divino del báculo es $\sqrt[3]{2 \times 3 \times 4}$.
Entrada 3
18 6 ...2.1.0.1..1.0..1 011 6 111 4 010 12 121 7 101 5 10 3
Salida 3
121211203112120121
Subtareas
Sea $s = \sum_{i=1}^{m} |S_i|$, es decir, la suma de las longitudes de todas las cadenas de hechizos.
| Caso de prueba | $n\le$ | $s\le$ | Propiedad especial |
|---|---|---|---|
| $1\sim 3$ | $6$ | $20$ | |
| $4\sim 5$ | $501$ | $5$ | |
| $6$ | $501$ | $501$ | Todos los $V_i$ son iguales |
| $7$ | $501$ | $501$ | $V_i$ tiene como máximo $2$ valores distintos |
| $8$ | $501$ | $501$ | $V_i$ tiene como máximo $3$ valores distintos |
| $9\sim 11$ | $501$ | $501$ | $T$ consiste totalmente en . |
| $12\sim 13$ | $501$ | $501$ | $T$ tiene como máximo $3$ posiciones con . |
| $14\sim 16$ | $501$ | $501$ | |
| $17\sim 20$ | $1501$ | $1501$ |
Para el $100\%$ de los datos, se cumple que $1\le n, m, s \le 1501$ y $1\le V_i\le 10^9$.