狂野飙车 es el juego favorito de 小 L. A diferencia de otros jugadores aficionados, además de jugar, 小 L estudia a fondo el diseño del juego, por lo que tiene estrategias de juego poco habituales.

Descripción

小 L planea jugar $n$ partidas. En cada partida se utiliza un mapa, y 小 L elegirá un coche para completar la partida en ese mapa.

小 L tiene tres coches de carreras, representados respectivamente por las letras mayúsculas A, B y C. Hay cuatro tipos de mapas, representados respectivamente por las letras minúsculas x, a, b y c. El coche A no es adecuado para el mapa a, el coche B no es adecuado para el mapa b y el coche C no es adecuado para el mapa c. En cambio, el mapa x es adecuado para todos los coches. Los mapas adecuados para todos los coches son poco frecuentes: habrá como máximo $d$ de ellos.

Los mapas de las $n$ partidas se pueden describir mediante una cadena de letras minúsculas. Por ejemplo, S=xaabxcbc indica que 小 L planea jugar 8 partidas. Los mapas de las partidas 1 y 5 son de tipo x y son adecuados para todos los coches; los de las partidas 2 y 3 son de tipo a y no son adecuados para el coche A; los de las partidas 4 y 7 son de tipo b y no son adecuados para el coche B; los de las partidas 6 y 8 son de tipo c y no son adecuados para el coche C.

小 L tiene algunos requisitos especiales para el juego. Estos se pueden describir mediante cuádruplas $(i,h_i,j,h_j)$: si en la partida $i$ se utiliza un coche de modelo $h_i$, entonces en la partida $j$ se debe utilizar un coche de modelo $h_j$.

¿Puedes ayudar a 小 L a elegir el coche que utilizará en cada partida? Si hay varias soluciones, imprime cualquiera de ellas. Si no hay solución, imprime -1 (sin comillas).

Entrada

Lee los datos del archivo game.in.

La primera línea contiene dos enteros no negativos $n,d$.

La segunda línea contiene una cadena $S$.

Los significados de $n,d,S$ se indican en la descripción. La cadena $S$ contiene $n$ caracteres, de los cuales exactamente $d$ son la letra minúscula x.

La tercera línea contiene un entero positivo $m$, que indica que hay $m$ reglas de uso de los coches. Cada una de las siguientes $m$ líneas contiene una cuádrupla $i,h_i,j,h_j$, donde $i,j$ son enteros y $h_i,h_j$ son los caracteres a, b o c, con el significado indicado en la descripción.

Salida

Escribe la salida en el archivo game.out.

Imprime una línea.

Si no hay solución, imprime -1 (sin comillas).

Si hay solución, imprime una cadena de longitud $n$ que contenga únicamente las letras mayúsculas A, B y C, indicando cómo 小 L debe asignar los coches a las $n$ partidas. Si hay varias soluciones, imprime cualquiera de ellas.

Ejemplos

Entrada 1

3 1
xcc
1
1 A 2 B

Salida 1

ABA

Ejemplo 2

Consulta los archivos game/game2.in y game/game2.ans del directorio del concursante.

Nota

小 L planea jugar 3 partidas. El mapa de la partida 1 es de tipo x y es adecuado para todos los coches; los mapas de las partidas 2 y 3 son de tipo c y no son adecuados para el coche C.

小 L desea que, si se utiliza el coche A en la partida 1, se utilice el coche B en la partida 2.

Por tanto, asignar los coches A, B y A a las 3 partidas, respectivamente, satisface todas las condiciones.

Asignar los coches BBB o BAA a las 3 partidas en ese orden también satisface todas las condiciones y se considera una respuesta correcta. Sin embargo, asignar los coches AAB o ABC en ese orden no satisface todas las condiciones y, por tanto, no se considera una respuesta correcta.

Subtareas