狂野飙车 é o jogo favorito de 小L. Ao contrário dos outros jogadores amadores, 小L também estuda a conceção do jogo enquanto joga, pelo que tem estratégias de jogo diferentes das dos outros.

Descrição do problema

小L planeia disputar $n$ partidas. Cada partida utiliza um mapa, e 小L escolherá um carro para completar a partida nesse mapa.

小L tem três carros de corrida, representados pelas letras maiúsculas $A$, $B$ e $C$. Existem quatro tipos de mapas, representados pelas letras minúsculas $x$, $a$, $b$ e $c$. O carro $A$ não é adequado para o mapa $a$, o carro $B$ não é adequado para o mapa $b$, e o carro $C$ não é adequado para o mapa $c$. O mapa $x$ é adequado para todos os carros. Os mapas adequados para todos os carros são pouco frequentes: haverá, no máximo, $d$ desses mapas.

Os mapas das $n$ partidas podem ser descritos por uma cadeia de letras minúsculas. Por exemplo, $S=\texttt{xaabxcbc}$ significa que 小L planeia disputar 8 partidas: os mapas da primeira e da quinta partidas são do tipo $x$, adequado para todos os carros; os mapas da segunda e da terceira partidas são do tipo $a$, inadequado para o carro $A$; os mapas da quarta e da sétima partidas são do tipo $b$, inadequado para o carro $B$; e os mapas da sexta e da oitava partidas são do tipo $c$, inadequado para o carro $C$.

小L tem alguns requisitos especiais para o jogo, que podem ser descritos por quádruplos $(i,h_i,j,h_j)$: se utilizar o carro do modelo $h_i$ na partida $i$, terá de utilizar o carro do modelo $h_j$ na partida $j$.

Consegues ajudar 小L a escolher o carro a utilizar em cada partida? Se existirem várias soluções, apresenta qualquer uma delas. Se não existir solução, apresenta -1 (sem aspas).

Entrada

Lê os dados do ficheiro game.in.

A primeira linha da entrada contém dois inteiros não negativos $n,d$.

A segunda linha contém uma cadeia $S$.

Os significados de $n,d,S$ são os indicados na descrição do problema. A cadeia $S$ contém $n$ caracteres, dos quais exatamente $d$ são a letra minúscula $x$.

A terceira linha contém um inteiro positivo $m$, que indica o número de regras para a utilização dos carros. Cada uma das $m$ linhas seguintes contém um quádruplo $i,h_i,j,h_j$, em que $i,j$ são inteiros e $h_i,h_j$ são os caracteres $a$, $b$ ou $c$, com os significados indicados na descrição do problema.

Saída

Escreve a saída no ficheiro game.out.

Apresenta uma linha.

Se não existir solução, apresenta -1 (sem aspas).

Se existir solução, apresenta uma cadeia de comprimento $n$, composta apenas pelas letras maiúsculas $A$, $B$ e $C$, que descreva como 小L deve escolher os carros nas $n$ partidas. Se existirem várias soluções, basta apresentar qualquer uma delas.

Exemplos

Entrada 1

3 1
xcc
1
1 A 2 B

Saída 1

ABA

Exemplo 2

Consulta os ficheiros game/game2.in e game/game2.ans no diretório dos concorrentes.

Explicação do exemplo 1

小L planeia disputar 3 partidas. O mapa da primeira partida é do tipo $x$, adequado para todos os carros; os mapas da segunda e da terceira partidas são do tipo $c$, inadequado para o carro $C$.

小L deseja que, se utilizar o carro $A$ na primeira partida, utilize o carro $B$ na segunda.

Assim, atribuir os carros $A$, $B$ e $A$, respetivamente, às 3 partidas satisfaz todas as condições.

Atribuir às 3 partidas, por ordem, os carros BBB ou BAA também satisfaz todas as condições, pelo que estas respostas também são consideradas corretas. Porém, as atribuições AAB ou ABC não satisfazem todas as condições, pelo que não são consideradas corretas.

Subtarefas