Este problema es interactivo.
Taja puede ganar fácilmente este juego, pero todos sus amigos no pudieron. Ahora ella te ofrece jugar este juego.
El equipo de juego consiste en un campo de $n \times n$ ($5 \le n \le 40$), una pieza, dos monedas (COIN1, COIN2), dos dados con direcciones cardinales (DICE1, DICE2) y una gran cantidad de bloques del tamaño de una celda.
| Nombre | Número de caras | Caras |
|---|---|---|
| COIN1. Moneda de movimiento | 2 | SLIDE, RAM |
| COIN2. Moneda de modificación | 2 | PLACE, REMOVE |
| DICE1. Primer dado con direcciones | 4 | N (Norte), S (Sur), W (Oeste), E (Este) |
| DICE2. Segundo dado con direcciones | 8 | N (Norte), S (Sur), W (Oeste), E (Este), NW (Noroeste), NE (Noreste), SW (Suroeste), SE (Sureste) |
Antes del comienzo del juego, la pieza y algunos bloques se colocan en el campo. Luego, el jugador realiza movimientos de este tipo. Primero, el jugador elige una moneda y la lanza para determinar una acción. Luego, elige uno de los dados y lo lanza para determinar la dirección $dir$. Después de eso, ocurre una de las cuatro acciones:
| Cadena de moneda | Acción |
|---|---|
| SLIDE | Mueve la pieza a lo largo de las celdas vacías en la dirección $dir$, hasta que la pieza choque con un bloque o el borde del laberinto |
| RAM | Mueve la pieza a lo largo de las celdas vacías en la dirección $dir$, hasta que choque con un primer bloque. Luego mueve la pieza y el bloque en la misma dirección, hasta que el bloque en movimiento choque con otro bloque o el borde del campo |
| PLACE | Si la celda adyacente en la dirección $dir$ junto a la pieza está vacía y está dentro del campo, coloca un bloque en esta celda |
| REMOVE | Si la celda adyacente en la dirección $dir$ junto a la pieza contiene un bloque y está dentro del campo, elimina el bloque de esta celda |
El objetivo es colocar la pieza en la celda de meta.
Una consulta para este problema es un lanzamiento de moneda y un lanzamiento de dado.
Protocolo de interacción
Al principio, el interactor proporciona el tamaño del laberinto, el laberinto y las coordenadas de la celda de meta. Luego, ocurren las siguientes acciones de 4 pasos:
- El programa del jurado muestra las coordenadas de la pieza o informa que la pieza ha llegado a la celda de meta.
- Tu programa muestra el nombre de la moneda.
- El programa del jurado muestra el nombre de la acción en la moneda.
- Tu programa muestra el nombre del dado.
- El programa del jurado muestra el nombre de la dirección en el dado e información adicional para la acción "RAM".
Salida
La salida estándar debe consistir en un par de líneas: nombre de la moneda y nombre del dado. El nombre de la moneda es la cadena "COIN1" o "COIN2". El nombre del dado es la cadena "DICE1" o "DICE2".
No olvides limpiar (flush) la salida estándar después de imprimir cada línea.
Entrada
La primera línea de la entrada estándar contiene un número entero $n$ — el tamaño del laberinto. Las siguientes $n$ líneas contienen $n$ caracteres "." (ASCII 46) o "#" (ASCII 35), que denotan una celda vacía y una celda con un bloque, respectivamente.
La siguiente línea contiene dos números enteros $r_f$ y $c_f$ — el número de fila y el número de columna de la celda de meta. La esquina superior izquierda es $(1, 1)$, la inferior derecha es $(n, n)$. La celda de meta y la celda inicial están vacías.
Los siguientes grupos describen cada movimiento:
- La primera línea de un grupo contiene dos números enteros $r, c$ — el número de fila y el número de columna de la pieza, o $(-1, -1)$ si la pieza llega a la celda de meta.
- La siguiente línea contiene el nombre de la acción mostrada en la moneda.
- La siguiente línea contiene el nombre de la dirección mostrada en el dado.
- Si la acción actual es "RAM", las siguientes dos cadenas contienen dos números enteros $r_1, c_1$ y $r_2, c_2$, que denotan que la pieza choca con un bloque en las coordenadas $(r_1, c_1)$ y mueve ese bloque a la celda $(r_2, c_2)$.
La dirección norte corresponde a un número de fila decreciente. El sur a un número de fila creciente. La dirección oeste a un número de columna decreciente. La dirección este a un número de columna creciente.
Cada lado de cualquier moneda o dado se muestra con la misma probabilidad.
Ejemplos
Entrada 1
5 #.... ..... ..... ..... ..#.. 4 3 1 5 PLACE W 1 5 RAM S 6 5 6 5 5 5 RAM W 5 3 5 1 5 2 PLACE NE 5 2 RAM NE 4 3 2 5 3 4 REMOVE NE 3 4 PLACE S 3 4 SLIDE W 3 1 RAM S 5 1 5 1 4 1 SLIDE E -1 -1
Salida 1
COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN2 DICE2 COIN1 DICE2 COIN2 DICE2 COIN2 DICE1 COIN1 DICE1 COIN1 DICE1 COIN1 DICE1
Figura 1. Representación de una moneda y un dado utilizados en el juego.