狂野飙车 jest ulubioną grą małego L. W odróżnieniu od innych amatorów mały L, oprócz grania, dobrze zna się również na badaniu konstrukcji gier, dlatego stosuje nietypowe strategie.

Treść zadania

Mały L planuje rozegrać $n$ wyścigów. W każdym wyścigu używa się jednej mapy, a mały L wybierze samochód, którym ukończy grę na tej mapie.

Mały L ma trzy samochody wyścigowe, oznaczone wielkimi literami A, B i C. Istnieją cztery rodzaje map, oznaczone małymi literami x, a, b i c. Samochód A nie nadaje się do mapy a, samochód B do mapy b, a samochód C do mapy c. Natomiast mapa x nadaje się dla wszystkich samochodów. Mapy odpowiednie dla wszystkich samochodów są rzadkie: będzie ich najwyżej $d$.

Mapy dla $n$ wyścigów można opisać łańcuchem małych liter. Na przykład $S=\texttt{xaabxcbc}$ oznacza, że mały L planuje 8 wyścigów. Mapy w wyścigach 1 i 5 są typu x i nadają się dla wszystkich samochodów; mapy w wyścigach 2 i 3 są typu a i nie nadają się dla samochodu A; mapy w wyścigach 4 i 7 są typu b i nie nadają się dla samochodu B; mapy w wyścigach 6 i 8 są typu c i nie nadają się dla samochodu C.

Mały L ma pewne szczególne wymagania dotyczące gry. Każde z nich można opisać czwórką $(i,h_i,j,h_j)$: jeśli w wyścigu $i$ zostanie użyty samochód typu $h_i$, to w wyścigu $j$ musi zostać użyty samochód typu $h_j$.

Czy potrafisz pomóc małemu L wybrać samochód do każdego wyścigu? Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich. Jeśli rozwiązanie nie istnieje, wypisz „-1” (bez cudzysłowów).

Wejście

Dane należy odczytać z pliku game.in.

Pierwszy wiersz wejścia zawiera dwie nieujemne liczby całkowite $n,d$.

Drugi wiersz wejścia zawiera łańcuch $S$.

Znaczenie $n,d,S$ opisano w treści zadania. Łańcuch $S$ zawiera $n$ znaków, z których dokładnie $d$ to małe litery x.

Trzeci wiersz wejścia zawiera dodatnią liczbę całkowitą $m$, oznaczającą liczbę reguł używania samochodów. Każdy z kolejnych $m$ wierszy zawiera czwórkę $i,h_i,j,h_j$, gdzie $i,j$ są liczbami całkowitymi, a $h_i,h_j$ są znakami a, b lub c. Ich znaczenie opisano w treści zadania.

Wyjście

Wynik należy zapisać do pliku game.out.

Wypisz jeden wiersz.

Jeśli rozwiązanie nie istnieje, wypisz „-1” (bez cudzysłowów).

Jeśli rozwiązanie istnieje, wiersz powinien zawierać łańcuch długości $n$, złożony wyłącznie z wielkich liter A, B i C, opisujący wybór samochodów przez małego L w tych $n$ wyścigach. Jeśli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład

Wejście 1

3 1
xcc
1
1 A 2 B

Wyjście 1

ABA

Przykład 2

Zobacz pliki game/game2.in i game/game2.ans w katalogu zawodnika.

Uwagi

Objaśnienie przykładu 1:

Mały L planuje 3 wyścigi. Mapa w pierwszym wyścigu jest typu x i nadaje się dla wszystkich samochodów, natomiast mapy w drugim i trzecim wyścigu są typu c i nie nadają się dla samochodu C.

Mały L chce, aby użycie samochodu A w pierwszym wyścigu pociągało za sobą użycie samochodu B w drugim wyścigu.

Przydzielenie samochodów A, B i A odpowiednio do tych 3 wyścigów spełnia wszystkie warunki.

Przydzielenie do kolejnych 3 wyścigów samochodów BBB lub BAA również spełnia wszystkie warunki i jest uznawane za poprawną odpowiedź. Natomiast przydziały AAB i ABC nie spełniają wszystkich warunków, więc nie są uznawane za poprawne odpowiedzi.

Podzadania