Las vacas se han aficionado mucho a las damas. Aunque disfrutan infinitamente, son pésimas en el final y piden ayuda.

En un tablero $N\times N$, $(4 \le N \le 30)$, busca la secuencia óptima que termina la partida en el siguiente turno. Las piezas solo se mueven por + y capturan saltando sobre una rival, que se retira inmediatamente. Ejemplo con $N=8$:

- + - + - + - +
+ - + - + - + -
- + - K - + - +
+ - + - + - + -
- o - o - + - +
+ - K - + - + -
- o - + - + - +
+ - K - + - K -

K marca las damas de Bessie; o, las piezas rivales. Siempre juega Bessie a continuación. Las damas saltan sucesivamente rivales en cualquier dirección diagonal y retiran las capturadas. Aquí la dama inferior izquierda salta las tres rivales, terminando la partida. La K móvil se marca >K<.

- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K -

De izquierda a derecha: original, tras movimiento 1, tras movimiento 2, tras movimiento 3.

Los movimientos recorren estas casillas:

  1 2 3 4 5 6 7 8
1 - + - + - + - +
2 + - + - + - + -
3 - + - K - + - +
4 + - * - + - + -
5 - o - o - + - +
6 * - K - * - + -
7 - o - + - + - +
8 + - K - + - K -

Fila, columna; inicio: $(8,3)$; movimientos: $(6,1)$, $(4,3)$, $(6,5)$.

Encuentra la secuencia que termina la partida en el tablero de entrada $N\times N$, si existe (resulta ser única). Hay al menos una dama y una pieza rival.

Entrada

• Línea 1: entero $N$.

• Líneas $2,\ldots,N+1$: la línea $i+1$ contiene $N$ caracteres -, +, K u o, que representan la fila $i$ de un tablero válido.

Salida

• Desde la línea 1: si es imposible, escribe impossible en una línea. Si existe, cada línea da dos enteros separados por espacio, las posiciones sucesivas de una dama cuyos movimientos ganan.

Ejemplos

Entrada 1

8
-+-+-+-+
+-+-+-+-
-+-K-+-+
+-+-+-+-
-o-o-+-+
+-K-+-+-
-o-+-+-+
+-K-+-K-

Salida 1

8 3
6 1
4 3
6 5

Autor del problema: Rob Kolstad, 2008