狂野飙车 ist das Lieblingsspiel von 小 L. Anders als andere Gelegenheitsspieler beschäftigt sich 小 L neben dem Spielen auch eingehend mit dem Spieldesign und hat deshalb eine ungewöhnliche Spielstrategie.

Aufgabenstellung

小 L plant $n$ Spiele. Jedes Spiel findet auf einer Karte statt, und 小 L wählt ein Auto, mit dem er das Spiel auf dieser Karte bestreitet.

小 L besitzt drei Rennwagen, die durch die Großbuchstaben A, B und C bezeichnet werden. Es gibt vier Kartentypen, bezeichnet durch die Kleinbuchstaben x, a, b und c. Rennwagen A eignet sich nicht für Karten vom Typ a, Rennwagen B nicht für Karten vom Typ b und Rennwagen C nicht für Karten vom Typ c. Auf Karten vom Typ x können dagegen alle Rennwagen fahren. Karten, auf denen alle Rennwagen fahren können, sind selten; es gibt höchstens $d$ davon.

Die Karten der $n$ Spiele lassen sich durch eine Zeichenkette aus Kleinbuchstaben beschreiben. Beispielsweise bedeutet $S=\text{xaabxcbc}$, dass 小 L 8 Spiele plant. Die Karten im 1. und 5. Spiel haben den Typ x und eignen sich für alle Rennwagen. Die Karten im 2. und 3. Spiel haben den Typ a und eignen sich nicht für Rennwagen A. Die Karten im 4. und 7. Spiel haben den Typ b und eignen sich nicht für Rennwagen B. Die Karten im 6. und 8. Spiel haben den Typ c und eignen sich nicht für Rennwagen C.

小 L hat einige besondere Anforderungen an die Spiele. Jede lässt sich durch ein Quadrupel $(i,h_i,j,h_j)$ beschreiben: Wird im $i$-ten Spiel ein Wagen vom Typ $h_i$ verwendet, muss im $j$-ten Spiel ein Wagen vom Typ $h_j$ verwendet werden.

Kannst du 小 L helfen, für jedes Spiel einen Rennwagen zu wählen? Gibt es mehrere Möglichkeiten, gib eine beliebige aus. Gibt es keine Lösung, gib -1 aus (ohne Anführungszeichen).

Eingabe

Lies die Daten aus der Datei game.in.

Die erste Eingabezeile enthält zwei nichtnegative ganze Zahlen $n,d$.

Die zweite Eingabezeile enthält eine Zeichenkette $S$.

Die Bedeutung von $n,d,S$ ist in der Aufgabenstellung beschrieben. $S$ besteht aus $n$ Zeichen, von denen genau $d$ der Kleinbuchstabe x sind.

Die dritte Eingabezeile enthält eine positive ganze Zahl $m$, die Anzahl der Regeln zur Fahrzeugwahl. Jede der folgenden $m$ Zeilen enthält ein Quadrupel $i,h_i,j,h_j$. Dabei sind $i,j$ ganze Zahlen und $h_i,h_j$ die Zeichen a, b oder c; ihre Bedeutung ist in der Aufgabenstellung beschrieben.

Ausgabe

Schreibe die Ausgabe in die Datei game.out.

Gib eine Zeile aus.

Gibt es keine Lösung, gib -1 aus (ohne Anführungszeichen).

Andernfalls enthält die Zeile eine Zeichenkette der Länge $n$, die nur aus den Großbuchstaben A, B und C besteht und angibt, welche Rennwagen 小 L in den $n$ Spielen verwendet. Gibt es mehrere Lösungen, genügt eine beliebige davon.

Beispiele

Eingabe 1

3 1
xcc
1
1 A 2 B

Ausgabe 1

ABA

Beispiel 2

Siehe game/game2.in und game/game2.ans im Teilnehmerverzeichnis.

Hinweis

小 L plant 3 Spiele. Die Karte im 1. Spiel hat den Typ x und eignet sich für alle Rennwagen. Die Karten im 2. und 3. Spiel haben den Typ c und eignen sich nicht für Rennwagen C.

小 L verlangt: Wird im 1. Spiel Rennwagen A verwendet, muss im 2. Spiel Rennwagen B verwendet werden.

Werden für diese 3 Spiele der Reihe nach die Rennwagen A, B und A gewählt, sind alle Bedingungen erfüllt.

Auch die Belegungen BBB oder BAA erfüllen alle Bedingungen und gelten als korrekte Antworten. Die Belegungen AAB oder ABC erfüllen dagegen nicht alle Bedingungen und gelten deshalb nicht als korrekte Antworten.

Teilaufgaben