Krowy z zapałem grają w warcaby. Mimo nieskończonej radości fatalnie radzą sobie w końcówce i proszą o pomoc.

Dla planszy $N\times N$, $(4 \le N \le 30)$, znajdź optymalną sekwencję kończącą grę w następnej turze. Piony poruszają się tylko po + i biją przez przeskoczenie przeciwnika, od razu usuwanego. Przykład $N=8$:

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

K to damki Bessie, o to piony przeciwnika. Następna zawsze rusza Bessie. Damki kolejno przeskakują przeciwników w dowolnym kierunku po przekątnej, usuwając zbite piony. Tutaj dolna lewa damka przeskakuje wszystkie trzy piony i kończy grę. Ruchoma K ma oznaczenie >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 -

Od lewej: stan pierwotny, po ruchu 1, po ruchu 2, po ruchu 3.

Ruchy przechodzą przez te pola:

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

Rząd, kolumna; początek: $(8,3)$; ruchy: $(6,1)$, $(4,3)$, $(6,5)$.

Znajdź sekwencję kończącą grę dla wejściowej planszy $N\times N$, jeśli istnieje (okazuje się jedyna). Jest co najmniej jedna damka i jeden pion przeciwnika.

Wejście

• Wiersz 1: liczba całkowita $N$.

• Wiersze $2,\ldots,N+1$: wiersz $i+1$ zawiera $N$ znaków -, +, K lub o, opisujących rząd $i$ poprawnej planszy.

Wyjście

• Od wiersza 1: jeśli niemożliwe, wypisz impossible w osobnym wierszu. Inaczej każdy wiersz zawiera dwie liczby całkowite oddzielone spacją, kolejne pozycje damki, której ruchy wygrywają.

Przykład

Wejście 1

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

Wyjście 1

8 3
6 1
4 3
6 5

Autor zadania: Rob Kolstad, 2008