Winning Checkers

The cows have taken up checkers with a vengeance. They love playing, but they are hopeless at the endgame and need your help.

You are given an $N \times N$ ($4 \le N \le 500$) checkerboard. Playable squares are marked + and the remaining squares are marked -. Two kinds of pieces sit on playable squares: Bessie's kings (K) and the opponent's checkers (o). Bessie moves next, and the board always has at least one king and at least one opponent checker.

A king captures by jumping diagonally over an adjacent opponent checker and landing on the empty playable square immediately beyond it, in any of the four diagonal directions — the ordinary checkers jump. The jumped checker is removed at once. A king may chain many jumps in a single turn, and in a winning turn every move is a jump.

Bessie ends the game this turn if a single king can capture all of the opponent's checkers in one unbroken chain of jumps. A jump is legal only when the landing square is inside the board and empty — it holds no checker and no other king. The other kings never move; they only block landing squares and are never jumped.

For example, on the board below ($N = 8$) the lower-left king can jump across all three opponent checkers in turn and finish the game:

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

Rows are numbered $1$ to $N$ from top to bottom and columns $1$ to $N$ from left to right. Here the winning king starts at row $8$, column $3$, then lands on $(6, 1)$, $(4, 3)$, and $(6, 5)$, removing one opponent checker with each jump.

Write a program that finds such a game-ending sequence when one exists.

• Line $1$: a single integer $N$.
• Lines $2$ to $N + 1$: line $i + 1$ contains $N$ characters, each one of -, +, K, or o, describing row $i$ of the board. The first board line always begins with -.

If no king can capture every opponent checker, output impossible on a line by itself.

Otherwise output the lexicographically smallest winning sequence. Print one line for each square the winning king occupies — its starting square first, then its square after each jump — as two space-separated integers row col (both 1-indexed).

Every winning sequence contains exactly one jump per opponent checker, so all of them have the same number of lines and "smallest" is unambiguous: compare two candidate sequences line by line from the top, and at the first line where they differ prefer the smaller row, or the smaller column when the rows are equal.