Las vacas se han tomado en serio el juego de damas. Desafortunadamente, a pesar su gozo ilimitado en jugar, ellas son terribles al final del juego y desean que usted les ayude.

Dado un tablero de damas ~N x N~ ~(4 \leq N \leq 30)~, determine el conjunto optimo de movimientos para terminar el juego en la siguiente movida. Las damas no se mueven únicamente en los cuadrados ~'+'~ y capturan saltando 'sobre' una pieza del oponente en la manera tradicional. La pieza es removida tan pronto es saltada. Vea el ejemplo a continuación donde ~N~=8:

- + - + - + - +    Las K's representan reinas de Bessie; las o's representan las
+ - + - + - + -    damas del oponente. Bessie siempre hace el siguiente 
- + - K - + - +    movimiento.
+ - + - + - + -    Las reinas saltan encima de damas del oponente en cualquier
- o - o - + - +    dirección diagonal (y remueven las piezas saltadas).
+ - K - + - + -  
- o - + - + - +    Para este tablero, la mejor solución requiere que la Reina
+ - K - + - K -    inferior izquierda salte sucesivamente encima de tres de las
                   damas del oponente, por lo tanto terminando el juego (moviendo
                   la reina marcada como >K<):


   Original         Después de mov 1   Después de mov 2    Después de mov 3
- + - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ - + - + - + -     + - + - + - + -    + - + - + - + -     + - + - + - + -
- + - K - + - +     - + - K - + - +    - + - K - + - +     - + - K - + - +
+ - + - + - + -     + - + - + - + -    + ->K<- + - + -     + - + - + - + -
- o - o - + - +     - o - o - + - +    - + - o - + - +     - + - + - + - +
+ - K - + - + -    >K<- K - + - + -    + - K - + - + -     + - K ->K<- + -
- o - + - + - +     - + - + - + - +    - + - + - + - +     - + - + - + - +
+ ->K<- + - K -     + - + - + - K -    + - K - + - K -     + - K - + - K -

Los movimientos recorrieron  estos cuadrados:

  1 2 3 4 5 6 7 8            F C
1 - + - + - + - +    inicio: 8 3
2 + - + - + - + -    movida: 6 1
3 - + - K - + - +    movida: 4 3
4 + - * - + - + -    movida: 6 5
5 - o - o - + - +
6 * - K - * - + - 
7 - o - + - + - + 
8 + - K - + - K –

Escriba un programa que determine la secuencia (que resulta ser única) que termina el juego para un tablero de entrada ~N x N~ si existe. Siempre hay al menos una reina y al menos una dama del oponente en el tablero.

Entrada

• Línea ~1:~ Un solo entero: ~N~.

• Líneas ~2..N+1:~ La línea ~i+1~ contiene ~N~ caracteres ('-', '+', 'K', 'o') que representan la fila ~i~ de un tablero apropiado. La línea 2 siempre comienza con '-'.

Ejemplo de Entrada

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

Salida

• Líneas ~1..?:~ Si no hay una secuencia ganadora de saltos, dé como salida "impossible" en una línea en sí. Si existe una secuencia tal, cada línea contiene dos enteros separados por espacio que representan ubicaciones sucesivas de los movimientos de una reina que ganaran el juego.

Ejemplo de Salida

8 3
6 1
4 3
6 5