Die Kühe spielen mit Begeisterung Dame. Trotz grenzenlosen Spaßes sind sie im Endspiel schlecht und brauchen Hilfe.

Finde für ein Brett $N\times N$, $(4 \le N \le 30)$, die optimale Zugfolge, die das Spiel im nächsten Zug beendet. Figuren bewegen sich nur auf + und schlagen durch Überspringen eines Gegners, der sofort entfernt wird. Beispiel mit $N=8$:

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

K bezeichnet Bessies Damen, o gegnerische Figuren. Bessie ist immer als Nächste am Zug. Damen überspringen Gegner nacheinander in beliebigen Diagonalrichtungen und entfernen geschlagene Figuren. Hier überspringt die Dame links unten alle drei Gegner und beendet das Spiel. Die bewegte K ist als >K< markiert.

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

Von links: ursprünglich, nach Bewegung 1, nach Bewegung 2, nach Bewegung 3.

Die Züge durchlaufen diese Felder:

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

Zeile, Spalte; Start: $(8,3)$; Bewegungen: $(6,1)$, $(4,3)$, $(6,5)$.

Finde für das Eingabebrett $N\times N$ eine das Spiel beendende Folge, falls vorhanden (sie ist dann tatsächlich eindeutig). Es gibt mindestens eine Dame und eine gegnerische Figur.

Eingabe

• Zeile 1: Ganzzahl $N$.

• Zeilen $2,\ldots,N+1$: Zeile $i+1$ enthält $N$ Zeichen -, +, K oder o für Reihe $i$ eines gültigen Bretts.

Ausgabe

• Ab Zeile 1: falls unmöglich, impossible allein in einer Zeile. Sonst enthält jede Zeile zwei Ganzzahlen durch Leerzeichen getrennt, aufeinanderfolgende Positionen einer Dame, deren Züge gewinnen.

Beispiele

Eingabe 1

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

Ausgabe 1

8 3
6 1
4 3
6 5

Aufgabenautor: Rob Kolstad, 2008