As vacas se dedicam com entusiasmo às damas. Apesar da diversão infinita, são péssimas no final e pedem ajuda.

Num tabuleiro $N\times N$, $(4 \le N \le 30)$, encontre a sequência ótima que encerra a partida no próximo turno. As peças só se movem por + e capturam saltando sobre uma adversária, removida imediatamente. Exemplo para $N=8$:

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

K indica as damas de Bessie e o as peças adversárias. Bessie sempre joga em seguida. As damas saltam adversárias sucessivamente em qualquer diagonal, removendo as capturadas. Aqui a dama inferior esquerda salta as três adversárias, encerrando a partida. A K móvel é marcada >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 -

Da esquerda à direita: original, após movimento 1, após movimento 2, após movimento 3.

Os movimentos percorrem estas casas:

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

Linha, coluna; início: $(8,3)$; movimentos: $(6,1)$, $(4,3)$, $(6,5)$.

Encontre a sequência que encerra a partida no tabuleiro de entrada $N\times N$, se existir (é, de fato, única). Há ao menos uma dama e uma peça adversária.

Entrada

• Linha 1: inteiro $N$.

• Linhas $2,\ldots,N+1$: a linha $i+1$ contém $N$ caracteres -, +, K ou o, representando a linha $i$ de um tabuleiro válido.

Saída

• Desde a linha 1: se impossível, escreva impossible sozinho numa linha. Caso exista, cada linha contém dois inteiros separados por espaço, posições sucessivas de uma dama cujos movimentos vencem a partida.

Exemplos

Entrada 1

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

Saída 1

8 3
6 1
4 3
6 5

Autor do problema: Rob Kolstad, 2008