Les vaches se passionnent pour les dames. Malgré leur plaisir infini, elles sont très mauvaises en fin de partie et demandent votre aide.

Pour un damier $N\times N$, $(4 \le N \le 30)$, trouvez la suite optimale qui termine la partie au prochain tour. Les pièces ne se déplacent que sur les cases + et prennent en sautant par-dessus l'adversaire, retiré immédiatement. Exemple avec $N=8$ :

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

K désigne les dames de Bessie, o les pièces adverses. Bessie joue toujours ensuite. Les dames sautent successivement sur les adversaires dans toute direction diagonale, retirant les pièces prises. Ici, la dame en bas à gauche saute les trois adversaires, terminant la partie. La K mobile est marquée >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 -

De gauche à droite : état initial, après mouvement 1, après mouvement 2, après mouvement 3.

Les déplacements traversent ces cases :

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

Ligne, colonne ; départ : $(8,3)$ ; déplacements : $(6,1)$, $(4,3)$, $(6,5)$.

Trouvez la suite qui termine la partie sur le damier d'entrée $N\times N$, si elle existe (elle est alors unique). Il y a au moins une dame et une pièce adverse.

Entrée

• Ligne 1 : entier $N$.

• Lignes $2,\ldots,N+1$ : la ligne $i+1$ contient $N$ caractères -, +, K ou o, représentant la rangée $i$ d'un damier valide.

Sortie

• À partir de la ligne 1 : si impossible, impossible seul sur une ligne. Sinon chaque ligne contient deux entiers séparés par un espace, les positions successives d'une dame dont les déplacements gagnent la partie.

Exemples

Entrée 1

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

Sortie 1

8 3
6 1
4 3
6 5

Auteur du problème : Rob Kolstad, 2008