En un tablero de ajedrez de $10$ filas por $9$ columnas, se está jugando un juego llamado "Qi Men Xiang Qi". Cada bando tiene varias piezas, y las diferentes piezas tienen diferentes características. Usamos las coordenadas $(x, y)$ para representar la posición en la $x$-ésima fila y la $y$-ésima columna del tablero.
Nuestro bando tiene varias Torres (Rooks) y varios Caballos (Knights), así como la habilidad Cambio de forma (Shape-shifting). Los métodos de movimiento de estos dos tipos de piezas y la habilidad se describen a continuación:
- Supongamos que la Torre está ubicada en las coordenadas $(a, b)$. Si se mueve a las coordenadas $(c, d)$ en el tablero en una acción, se deben cumplir las siguientes condiciones:
- No hay piezas aliadas en $(c, d)$. Es decir, no puede capturar piezas aliadas ni superponerse con ellas.
- $c = a$ o $d = b$, pero $(a, b) \neq (c, d)$. Es decir, puede moverse a lo largo de la fila o columna en la que se encuentra, pero no puede permanecer en la misma posición.
- No puede haber ninguna otra pieza entre $(a, b)$ y $(c, d)$. Es decir, no puede saltar sobre otras piezas mientras se mueve.
- Supongamos que el Caballo está ubicado en las coordenadas $(a, b)$. Si se mueve a las coordenadas $(c, d)$ en el tablero en una acción, se deben cumplir las siguientes condiciones:
- No hay piezas aliadas en $(c, d)$. Es decir, no puede capturar piezas aliadas ni superponerse con ellas.
- $\{|a - c|, |b - d|\} = \{1, 2\}$. Aquí, $\{\dots\}$ denota un conjunto no ordenado. Esto corresponde al movimiento tradicional del ajedrez en forma de "L" (ten en cuenta que no hay bloqueo de caballo en este problema).
- Cambio de forma: Se puede usar como una acción para intercambiar las posiciones de dos piezas aliadas cualesquiera. No hay límite en el número de usos.
El enemigo tiene varios Slimes. Los Slimes no pueden moverse, pero tienen las siguientes características:
- Supongamos que el Slime está ubicado en las coordenadas $(a, b)$. Cuando es capturado y eliminado, se dividirá inmediatamente, generando un Slime en cada una de las cuatro posiciones adyacentes (arriba, abajo, izquierda, derecha). Específicamente, en estas cuatro posiciones adyacentes, no se generarán nuevos slimes en posiciones que ya tengan otras piezas o que estén fuera de los límites del tablero.
- Los Slimes generados por división tienen las mismas características de división y no hay límite en el número de divisiones.
Después de mover las piezas, si se superponen con piezas enemigas, se activa una captura que elimina las piezas enemigas. La condición de victoria del juego es capturar todos los Slimes enemigos, asegurando que no queden piezas enemigas en el tablero.
Mientras jugaba, Xiao Biao descubrió que, aunque el enemigo no puede mover sus piezas, sigue siendo difícil para nuestro bando capturar limpiamente a los Slimes, ya que son numerosos y se dividen de manera muy eficiente, lo que a menudo lleva a que se generen más slimes, haciendo difícil para Xiao Biao determinar si la victoria es posible en este juego. Ha acudido a ti, que eres hábil en estrategia y análisis, esperando que puedas ayudarlo a determinar si existe una estrategia para lograr la victoria en a lo sumo $10^4$ movimientos. Si existe tal estrategia ganadora, imprime las operaciones para cada paso.
Entrada
La entrada consta de $10$ líneas, cada una con una cadena de longitud $9$, que representa la situación del tablero. Donde el carácter . representa una posición vacía; el carácter C representa nuestra Torre; el carácter M representa nuestro Caballo; y el carácter S representa el Slime enemigo.
Cada tipo de carácter puede aparecer varias veces. Los datos garantizan que hay al menos un Slime en el tablero y al menos una pieza aliada.
Salida
Si no hay estrategia para ganar en a lo sumo $10^4$ movimientos:
- Imprime una sola línea con la cadena
WuJie.
Si existe una estrategia para ganar en a lo sumo $10^4$ movimientos:
- Primero, imprime una sola línea con la cadena
YouJie. - A continuación, imprime un entero $s$, que representa el número de acciones.
- Luego, imprime $s$ líneas, cada una con cuatro enteros $a, b, c, d$, indicando que la pieza aliada actualmente en $(a, b)$ se mueve a la posición $(c, d)$. Específicamente, si ambas posiciones $(a, b)$ y $(c, d)$ ya tienen piezas aliadas, esta acción se considera Cambio de forma, indicando que estas dos piezas intercambian posiciones.
- Tu estrategia debe asegurar que después de completar todas las acciones, no queden Slimes en el tablero.
Si hay múltiples soluciones válidas diferentes, se puede imprimir cualquiera de ellas.
Las soluciones que no cumplan con los requisitos de formato, no cumplan con las reglas de movimiento de las piezas o indiquen que no hay ninguna pieza en la posición $(a, b)$ se considerarán incorrectas.
Ejemplos
Entrada 1
...CSC... ...CCCM.. ......... ......... ......... ......... ......... ......... ......... .........
Salida 1
YouJie 6 1 4 1 3 1 3 1 2 1 2 1 1 1 1 2 4 2 4 1 4 2 7 1 5
Entrada 2
SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSSSSSS SSSSCSSSS
Salida 2
WuJie
Nota
La salida para el ejemplo $1$ demuestra múltiples operaciones válidas y finalmente captura todos los slimes.
- Los pasos $1$ a $3$ muestran a la Torre en $(1, 4)$ moviéndose hacia la izquierda, eligiendo moverse una casilla a la vez, y finalmente aterrizando en $(1, 1)$.
- El paso $4$ demuestra la operación de Cambio de forma, intercambiando la Torre en $(1, 1)$ con la Torre en $(2, 4)$.
- El paso $5$ muestra a la Torre en $(2, 4)$ moviéndose hacia arriba hasta $(1, 4)$.
- El paso final muestra al Caballo saltando de $(2, 7)$ a $(1, 5)$ para capturar al único Slime. Como no hay posiciones vacías válidas adyacentes al Slime después de esto, no puede dividirse. Se gana el juego.