La guerre de résistance du continent de Bezorath contre l'invasion de la Légion des Désastres est entrée dans une phase d'impasse. Les elfes, qui vivent sur le continent de Bezorath depuis des générations, ont commencé à rechercher des artefacts laissés par les dieux de l'Antiquité, tentant d'utiliser leurs pouvoirs mystérieux pour vaincre la Légion des Désastres.

Après avoir payé un prix terrible, les elfes ont récupéré un sceptre divin encore intact sur un champ de bataille antique semé d'embûches. Cependant, après la « Guerre du Crépuscule des Dieux », considérée comme un tabou dans tous les livres d'histoire, les gemmes arcaniques incrustées sur le sceptre sont devenues incomplètes et son pouvoir divin est presque épuisé. Les hauts dirigeants elfes ont décidé, avec le soutien de toute la nation, de collecter les gemmes arcaniques restantes et d'offrir une récompense généreuse aux artisans capables de réparer ce sceptre.

En tant que 501e héritier de la lignée des arts divins, vous avez accepté cette mission ardue et sacrée. Le sceptre est incrusté de $n$ gemmes arcaniques de gauche à droite. Il existe $10$ types de gemmes arcaniques, représentées par les chiffres 0123456789. Certaines positions sont incomplètes et marquées par .. Vous devez remplir chaque partie manquante avec des gemmes arcaniques valides (le nombre de chaque type de gemme est illimité, et vous ne pouvez pas remplacer les gemmes déjà présentes). Le livre de magie antique enregistre $m$ types d'incantations $(S_i, V_i)$, où $S_i$ est une chaîne de chiffres non vide et $V_i$ est le pouvoir divin que cette combinaison peut activer.

La valeur initiale du pouvoir divin du sceptre est $\mathrm{Magic} = 1$. Chaque fois qu'une séquence continue de gemmes dans le sceptre est égale à $S_i$, la valeur du pouvoir divin $\mathrm{Magic}$ est multipliée par $V_i$. Cependant, si le sceptre contient trop d'incantations, il perd sa pureté et son pouvoir diminue : soit $c$ le nombre d'incantations contenues dans le sceptre (si les catégories d'incantations sont identiques mais apparaissent à des positions différentes, elles sont comptées séparément), la valeur finale du pouvoir divin du sceptre est $\sqrt[c]{\mathrm{Magic}}$. (Si $c = 0$, la valeur finale du pouvoir divin est $1$.)

Par exemple, s'il existe deux incantations $(01, 3)$ et $(10, 4)$, alors le pouvoir divin du sceptre 0101 est $\sqrt[3]{3 \times 4 \times 3}$.

Vous devez maximiser la valeur finale du pouvoir divin du sceptre réparé. Affichez n'importe quelle solution valide.

Entrée

La première ligne contient deux entiers positifs $n$ et $m$, représentant le nombre de gemmes et le nombre d'incantations.

La deuxième ligne contient une chaîne $T$ de longueur $n$, représentant le sceptre initial.

Les $m$ lignes suivantes contiennent chacune une chaîne de chiffres non vide $S_i$ et un entier positif $V_i$, représentant chaque type d'incantation.

Sortie

Affichez les gemmes incrustées sur le sceptre final de gauche à droite. S'il existe plusieurs solutions, n'importe laquelle suffit.

Exemples

Entrée 1

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

Sortie 1

2019

Remarque 1

La valeur finale du pouvoir divin du sceptre est $2$.

Entrée 2

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

Sortie 2

11012

Remarque 2

La valeur finale du pouvoir divin du sceptre est $\sqrt[3]{2 \times 3 \times 4}$.

Entrée 3

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

Sortie 3

121211203112120121

Sous-tâches

Soit $s = \sum_{i=1}^{m} |S_i|$, la somme des longueurs de toutes les chaînes d'incantations.

Pour $100\%$ des données, on a $1\le n, m, s \le 1501$ et $1\le V_i\le 10^9$.