狂野飙车 est le jeu préféré de 小 L. Contrairement aux autres joueurs amateurs, 小 L étudie également la conception du jeu pendant son temps libre ; il possède donc une stratégie de jeu bien à lui.

小 L prévoit de jouer $n$ parties. Chaque partie utilise un circuit, et 小 L choisit une voiture pour terminer la partie sur ce circuit.

小 L possède trois voitures de course, désignées par les lettres majuscules $A$, $B$ et $C$. Il existe quatre types de circuits, désignés par les lettres minuscules $x$, $a$, $b$ et $c$. La voiture $A$ ne convient pas aux circuits $a$, la voiture $B$ ne convient pas aux circuits $b$, et la voiture $C$ ne convient pas aux circuits $c$. Les circuits $x$ conviennent à toutes les voitures. Les circuits qui conviennent à toutes les voitures sont rares : il y en a au plus $d$.

Les circuits des $n$ parties peuvent être décrits par une chaîne de lettres minuscules. Par exemple, $S=\text{xaabxcbc}$ signifie que 小 L prévoit de jouer 8 parties : les circuits des première et cinquième parties sont de type $x$ et conviennent à toutes les voitures ; ceux des deuxième et troisième parties sont de type $a$ et ne conviennent pas à la voiture $A$ ; ceux des quatrième et septième parties sont de type $b$ et ne conviennent pas à la voiture $B$ ; ceux des sixième et huitième parties sont de type $c$ et ne conviennent pas à la voiture $C$.

小 L a certaines exigences particulières concernant le jeu. Une exigence est décrite par un quadruplet $(i,h_i,j,h_j)$ : si la voiture de modèle $h_i$ est utilisée lors de la $i$-ième partie, la voiture de modèle $h_j$ doit être utilisée lors de la $j$-ième partie.

Pouvez-vous aider 小 L à choisir la voiture à utiliser pour chaque partie ? Si plusieurs solutions existent, affichez-en une quelconque. S'il n'existe aucune solution, affichez -1 (sans guillemets).

Entrée

Lisez les données dans le fichier game.in.

La première ligne contient deux entiers non négatifs $n,d$.

La deuxième ligne contient une chaîne $S$.

La signification de $n,d,S$ est donnée dans l'énoncé. La chaîne $S$ contient $n$ caractères, dont exactement $d$ sont la lettre minuscule $x$.

La troisième ligne contient un entier positif $m$, indiquant le nombre de règles d'utilisation des voitures. Chacune des $m$ lignes suivantes contient un quadruplet $i,h_i,j,h_j$, où $i,j$ sont des entiers et $h_i,h_j$ sont les caractères $a$, $b$ ou $c$, avec la signification donnée dans l'énoncé.

Sortie

Écrivez la sortie dans le fichier game.out.

Affichez une ligne.

S'il n'existe aucune solution, affichez -1 (sans guillemets).

Sinon, affichez une chaîne de longueur $n$ composée uniquement des lettres majuscules $A$, $B$ et $C$, décrivant le choix des voitures de 小 L pour les $n$ parties. Si plusieurs solutions existent, vous pouvez en afficher une quelconque.

Exemples

Entrée 1

3 1
xcc
1
1 A 2 B

Sortie 1

ABA

Exemple 2

Voir les fichiers game/game2.in et game/game2.ans dans le répertoire des candidats.

Remarque

小 L prévoit de jouer 3 parties. Le circuit de la première partie est de type $x$ et convient à toutes les voitures ; les circuits des deuxième et troisième parties sont de type $c$ et ne conviennent pas à la voiture $C$.

小 L souhaite que, si la voiture $A$ est utilisée lors de la première partie, la voiture $B$ soit utilisée lors de la deuxième partie.

Choisir respectivement les voitures $A$, $B$ et $A$ pour ces 3 parties satisfait toutes les conditions.

Les choix BBB ou BAA pour les 3 parties satisfont également toutes les conditions et constituent donc aussi des réponses correctes. En revanche, les choix AAB ou ABC ne satisfont pas toutes les conditions et ne sont donc pas des réponses correctes.

Sous-tâches