Background

Many moons ago, in a galaxy much like our own, a young BrainSteel attempted to invent a board game. He believed that he, too, could find an amazingly simple set of rules that would generate wonderfully strategic gameplay. He drew up the first set of rules--it looked promising. He played with his thoughts, and noticed a minor inconsistency here, or a slight balance issue there. One by one, the rules started piling up, until they were at best arbitrary. Try as he might, the beautiful simplicity of Checkers or Go failed to shine through. His final creation, one bad enough he would only refer to it when speaking in the 3rd person, was given the temporary name "Quagmire." While perhaps not a brilliant board game, it ought to be a fun code golf!

The Rules of Quagmire

The game is played on an 8x8 board, and each player has 10 identical pieces. If player one has O pieces, and player 2 has X pieces, here is a portrayal of the game at the start (where . indicates a blank space):

 a b c d e f g h
+-+-+-+-+-+-+-+-+
|.|.|.|.|X|X|X|X| 8
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|X|X|X| 7
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|.|X|X| 6
+-+-+-+-+-+-+-+-+
|.|.|.|.|.|.|.|X| 5
+-+-+-+-+-+-+-+-+
|O|.|.|.|.|.|.|.| 4
+-+-+-+-+-+-+-+-+
|O|O|.|.|.|.|.|.| 3
+-+-+-+-+-+-+-+-+
|O|O|O|.|.|.|.|.| 2
+-+-+-+-+-+-+-+-+
|O|O|O|O|.|.|.|.| 1
+-+-+-+-+-+-+-+-+


Note that every space on the grid can be named with a letter and number, e.g. there is an O character on c2.

Players take turns in an alternating fashion.

On a player's turn, they may move in two ways:

• The player may move any piece in a straight line vertically, horizontally, or diagonally at most until they meet either another wall or piece. e.g. |X|.|.|O|.| => |.|.|X|O|.| for one move of length 2 horizontally. Note that the X piece cannot move any farther right, because there is a piece in the way.

• The player may use a piece to jump over a single, adjacent, and friendly piece. Jumps, like ordinary moves, may be horizontal, vertical, or diagonal. Under normal circumstances an enemy piece may not be jumped. e.g. |X|X|.| => |.|X|X|

If a piece cannot move to any of its surrounding spaces, and at least one of those adjacent spaces is occupied by an enemy piece, that piece is said to be in a state of Quagmire. If a player ends his turn with a piece in Quagmire, they lose the game.

Now for the more arbitrary rules:

• The bottom left player goes first.

• Each player must make exactly one move per turn. (No pass!)

• A piece may not be moved twice in a row, ever. e.g. if, on the first turn, player one moves the piece on c2, he may not move the same piece on his following turn.

• If the player to move has one or more pieces in Quagmire which may move, they must move one of those pieces.

• A piece may jump an enemy piece in the same way that it jumps a friendly piece if and only if that enemy piece is part of a closed loop (which may or may not start and end at a wall) of pieces of one color, and that loop is impenetrable by normal moves. If a piece jumps in this way, it must jump from inside the loop to the outside, or vice versa. Since this rule is weird, here is an example board:


a b c d e f g h
+-+-+-+-+-+-+-+-+
|.|.|.|O|X|.|.|X| 8
+-+-+-+-+-+-+-+-+
|.|.|.|.|X|.|.|X| 7
+-+-+-+-+-+-+-+-+
|.|.|.|.|X|.|.|.| 6
+-+-+-+-+-+-+-+-+
|X|.|.|.|.|X|X|X| 5
+-+-+-+-+-+-+-+-+
|O|O|O|O|.|.|.|.| 4
+-+-+-+-+-+-+-+-+
|.|.|.|O|X|.|.|.| 3
+-+-+-+-+-+-+-+-+
|.|.|.|O|.|.|O|.| 2
+-+-+-+-+-+-+-+-+
|O|O|O|O|.|.|.|.| 1
+-+-+-+-+-+-+-+-+


In this position, the X on a5 may legally jump to a3. In contrast, the O on d8 may NOT jump to f8, since the loop of X pieces is not fully closed -- the inside is accessible through the e5 - g7 diagonal. Also, note that the 'X' on e3 may not jump to c5 because this jump does not cross from outside the loop to the inside.

The Challenge

Your challenge is to allow two players at the same computer to play a game of Quagmire, adhering perfectly to the rules, against each other.

At every point in the game, your program should output the board as shown in the first example board, reflecting the current positions of all pieces on the board. You may choose any characters for the O, X, and . values, but the rest of the characters must be exactly as shown. You should also display, in a reasonable manner, whose turn it is!

Input

On a players' turn, you should accept a string of at least 5 bytes in the form X#<seperator>Y#. You may make reasonable adjustment to this format to suit your programming language. You may also assume that the input, while not necessarily a legal move, will be formatted correctly (no numbers greater than 8, etc). Your program should evaluate whether or not a move from X# on the board to Y# is legal for this player. If it is legal, your program should make the move and output the next board accordingly. If it is not legal, your program should output some falsy value (0 is perfectly reasonable--you do not need an explanation) and receive another input.

Winning

A player wins when the other player fails to relieve one of his pieces from Quagmire. Alternatively, a player wins when it is their opponent's turn and their opponent has no legal moves. Note that the first win condition takes precedence over the second. If I leave a piece in Quagmire at the end of the turn and simultaneously leave my opponent with no legal moves, I still lose the game. If the game is over after a player's move, you should output the winning board, the winning player's piece character (e.g. 'X') and some truthy value (Again, 1 is sufficient). At this point, your program may either terminate or restart the game.