Las reglas de este juego pueden diferir ligeramente del juego oficial.
Karen y sus amigos están compitiendo en un campeonato de juegos de mesa de alto riesgo, jugando al popular juego Codenames. Codenames es un juego con dos equipos opuestos: el equipo rojo y el equipo azul. Karen es miembro del equipo rojo.
El juego se juega en un tablero de tamaño $5 \times 5$ donde a cada una de las 25 celdas se le asigna (en secreto) uno de cuatro tipos. Hay un número fijo de celdas de cada tipo en el tablero:
- 9 celdas rojas (r);
- 8 celdas azules (b);
- 7 celdas neutrales (n);
- 1 celda asesina (x).
Los tipos reales de las celdas solo los conoce un jugador de cada equipo (llamado "spymaster"). Los otros jugadores inicialmente solo ven una cuadrícula de $5 \times 5$ llena de celdas cubiertas. Las celdas se revelarán a medida que avance el juego. Cada celda cubierta contiene el nombre de un objeto (lo cual resulta ser irrelevante para este problema).
Afortunadamente, Karen es la spymaster de su equipo, por lo que conoce la configuración real del tablero. Su responsabilidad es ayudar a sus compañeros de equipo a descubrir las celdas rojas, mientras los mantiene alejados de todas las demás celdas (especialmente la celda asesina). La forma en que puede hacerlo es anunciando una pista que consiste en:
- una palabra válida $w$ (de un diccionario de $n$ palabras);
- un número positivo $g$ (la cantidad de intentos que sus compañeros de equipo deben realizar).
Sus compañeros de equipo intentarán adivinar tantas celdas rojas como sea posible, dada la pista. Comienzan haciendo una primera suposición y revelan una de las celdas. Si la celda revelada es roja, pueden seguir adivinando; de lo contrario, su turno termina y el otro equipo comienza su turno. Un equipo gana el juego si se revelan todas las celdas con su color correspondiente, o si el otro equipo reveló la celda asesina.
Para ilustrar esto, consideremos el estado del juego a continuación (el que corresponde al ejemplo). La imagen de la izquierda muestra la vista del tablero de Karen. La imagen del medio muestra la vista del tablero de sus compañeros de equipo. Observe que algunas de las celdas están cubiertas para los compañeros de equipo de Karen, y solo Karen conoce sus tipos reales. El significado de la imagen de la derecha se explicará más adelante en el enunciado.
Originalmente, el objetivo de Karen era dar pistas relacionadas con los nombres de los objetos descritos en algunas de las celdas rojas, para que los compañeros de equipo supieran revelar solo esas celdas. Sin embargo, pronto se dio cuenta de que el juego no va muy bien y que el equipo azul podría ganarles en su próximo turno. Afortunadamente, ella y sus amigos han ideado un "esquema de trampa de emergencia" secreto para estas situaciones específicamente.
Comienzan asignando una letra a cada una de las 25 celdas, en orden de lectura por filas (como se ilustra arriba, en la imagen de la derecha). Luego, cuando Karen anuncia una palabra $w$ y un número $g$, sus compañeros de equipo harían lo siguiente:
- Recorrer cada una de las letras $w_i$ de la palabra $w$ en orden;
- Si $w_i$ no está asignada a ninguna celda o la celda asignada a $w_i$ ya está revelada, entonces no hacer nada; de lo contrario, adivinar la celda correspondiente a $w_i$.
Los compañeros de equipo repiten este procedimiento hasta que revelan todas las celdas correctas, cometen un error (revelan una celda que no es roja), ya han realizado todos los $g$ intentos, o todas las letras de $w$ han sido reveladas.
En el ejemplo anterior, Karen podría anunciar "actor 2" a su equipo. Su equipo primero adivinaría la celda (1, 1) (correspondiente a la letra a), saltaría la letra c ya que la celda (1, 3) ya está revelada, y luego adivinaría la celda (4, 5), ganando el juego (ya que las otras celdas rojas ya están reveladas).
Karen quiere usar este esquema para ganar el juego en un turno. Ella conoce el diccionario de todas las $n$ palabras válidas, así como el estado actual del juego. ¡Encuentra alguna pista que ella deba anunciar a su equipo para otorgarles la victoria!
Hay $q$ escenarios diferentes que debes resolver. El diccionario es el mismo para todos los escenarios, pero las configuraciones del tablero pueden diferir.
Entrada
La primera línea de la entrada contiene un número entero positivo $n$ ($1 \le n \le 100\,000$), el número de palabras válidas. Cada una de las siguientes $n$ líneas contiene una sola cadena de al menos una y como máximo 30 letras, representando las palabras en el diccionario.
La siguiente línea contiene un número entero positivo $q$ ($1 \le q \le 100\,000$), el número de escenarios. Luego, siguen $q$ líneas, cada una describiendo un tablero. Cada tablero está representado por una cuadrícula de $5 \times 5$ de letras del conjunto {r, b, n, x} (rojo/azul/neutral/asesino). Si la letra está en mayúscula, significa que la celda ya está revelada (de lo contrario, la celda está cubierta). Hay al menos una celda azul y una roja cubiertas, y la celda asesina siempre está cubierta; en otras palabras, el estado siempre indica un juego que aún no ha terminado.
Salida
Para cada uno de los $q$ escenarios, imprime la pista que consiste en una palabra $w$ y un número $g$ ($1 \le g \le 9$) que le da la victoria al equipo de Karen. Si no se puede anunciar tal pista para el escenario específico, imprime una sola palabra "IMPOSSIBLE" (sin comillas) en lugar de la pista. Si existen múltiples soluciones, se acepta cualquiera. Las respuestas para diferentes escenarios deben imprimirse en líneas separadas.
Ejemplos
Entrada 1
3 actor cheat zeta 1 rBBnR NRnbB nRRnR NRxBr nBRbB
Salida 1
actor 2
Nota
Tenga en cuenta que Karen no podría haber anunciado, por ejemplo, cheat 3, ya que su equipo terminaría revelando la celda en la posición (2, 3) y terminando su turno. Algunas otras soluciones correctas serían zeta 2 o actor 4.