Problem E
Frankenstein's Monster

When Victor Frankenstein is not busy with his experiments, he likes playing chess, as it is, in his opinion, a symbol of human creativity and intelligent thought. In line with this, he likes teaching his creations, alive or not, how to play the game.

Victor has been going to the pub recently, so much so that the locals have started calling him “Doctor Drunkenstein”. While inebriated, he challenges random visitors to defeat his creations. The parameters of the challenge are as follows:

• Victor will place a lone black king on an $8$ by $8$ chessboard, as well as $2$ white pieces. Note that these white pieces need not include a king.

• You win if you checkmate Victor’s king in the minimum number of moves.

• You lose if you:

  • make an illegal move

  • fail to checkmate in the minimum number of moves

  • have one of your pieces captured

  • cause a stalemate

Wanting to verify if his creations satisfy this claims, you try to take the challenge. Can you succeed?

Interaction

The input starts with $8$ lines, denoting the chessboard, each containing a string with $8$ characters, which can be any of

• “.”, denoting an empty square,

• “k”, denoting Victor’s king, and

• “K”, “Q”, “R”, “B”, “N”, denoting your king, queen, rook, bishop or knight, respectively.

It is guaranteed that Victor’s king, and exactly two of your pieces are on the board.

If you cannot win from this position, output “no-win” on a single line. Otherwise, output “win” on one line. In the next line, output the minimum number of moves you need to make to win the game. If your output here is incorrect, interaction will end, and you will receive Wrong Answer. Otherwise, you may begin making moves. It is guaranteed that if a position is winnable, it is winnable in at most $10^5$ moves.

To make a move, output three space-separated strings on a single line. The first must have only one character, and should be the piece you moved, using the same character as the input format. The second and third strings should be the source and destination squares of this piece, respectively. A square is composed of two characters: the row, which is a character from “a” to “h” from left to right, and the column, which is a number from “1” to “8” from bottom to top.

If you make an invalid move, or if you exceed your claimed move count, interaction will end, and you will get Wrong Answer. Otherwise, if you have still not won, you will receive Victor’s move as input, in the same format. Note that his piece is always written as “K”.

Notes

For the sake of completeness, here is a summary of the piece movement rules relevant to this problem. The pieces move as follows:

• A rook can move to (and attacks) a square that is on the same row or column

• A bishop can move to (and attacks) a square that is on the same diagonal.

• A queen can move to (and attacks) a square that is on the same row, column or diagonal.

• A knight can move to (and attacks) a square that is $2$ units in one direction, and $1$ unit in the perpendicular direction from its original square.

• A king can move to (and attacks) any of the $8$ squares adjacent to its current square.

Note that all pieces, except the knight, must have an unobstructed path from its starting to its ending square when making a move. Additionally, note that the king cannot move to a position that is being attacked by an enemy piece. A move cannot have the same starting square and ending square.

A player is checkmated if

1. it is their turn,

2. they cannot make any legal moves, and

3. they are being attacked.

Note that, under the constraints of this problem, only Victor can be checkmated.

If conditions $1$ and $2$, but not $3$ are met, then a stalemate occurs. Under the constraints of this problem, this is a win for Victor.

...k....
........
........
........
...K....
.....R..
........
........

win
8
R f3 f7

K d8 e8

R f7 a7

K e8 d8

K d4 c5

K d8 c8

K c5 d6

K c8 b8

R a7 c7

K b8 a8

K d6 c5

K a8 b8

K c5 b6

K b8 a8

R c7 c8

........
........
..k.....
........
........
......B.
.....K..
........

no-win