Le mucche si sono appassionate alla dama. Pur divertendosi infinitamente, sono pessime nel finale e chiedono aiuto.

Per una scacchiera $N\times N$, $(4 \le N \le 30)$, trova la sequenza ottimale che termina la partita al prossimo turno. Le pedine si muovono solo su + e catturano saltando sopra un'avversaria, subito rimossa. Esempio con $N=8$:

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

K indica le dame di Bessie, o le pedine avversarie. Tocca sempre a Bessie. Le dame saltano successivamente avversarie in qualsiasi diagonale, rimuovendo le catturate. Qui la dama in basso a sinistra salta tutte e tre le avversarie e termina la partita. La K che si muove è segnata >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 sinistra a destra: originale, dopo mossa 1, dopo mossa 2, dopo mossa 3.

Le mosse attraversano queste caselle:

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

Riga, colonna; partenza: $(8,3)$; mosse: $(6,1)$, $(4,3)$, $(6,5)$.

Trova la sequenza che termina la partita sulla scacchiera d'ingresso $N\times N$, se esiste (risulta unica). C'è almeno una dama e una pedina avversaria.

Input

• Riga 1: intero $N$.

• Righe $2,\ldots,N+1$: la riga $i+1$ contiene $N$ caratteri -, +, K oppure o per la riga $i$ di una scacchiera valida.

Output

• Dalla riga 1: se impossibile, scrivi impossible da solo su una riga. Altrimenti ogni riga contiene due interi separati da spazio, le posizioni successive di una dama che vince con tali mosse.

Esempi

Input 1

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

Output 1

8 3
6 1
4 3
6 5

Autore del problema: Rob Kolstad, 2008