B. Blokus Duo
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Blokus Duo is a 2-player version of the Blokus board game. The game is played on a $$$14 \times 14$$$ grid. The rows are numbered from 1 to 14 from top to bottom. The columns are numbered from 1 to 14 from left to right. The game uses two (purple and orange) sets of 21 different pieces.

Pieces can be flipped and/or rotated to produce different shapes, as illustrated below:

The two players take turn to place pieces. The player that has the purple pieces goes first. First, he/she must place a piece such that it covers the cell $$$(5, 5)$$$. The other (orange) player goes next. He/she must place a piece on empty cells such that it covers the cell $$$(10, 10)$$$.

After that, each piece must be placed such that:

  • It is placed on entirely empty cells.
  • It touches at least 1 corner of 1 or more existing piece(s) of the same color.
  • It does not touch any edge of any existing piece of the same color.

If a player cannot make any valid move, he/she must surrender so that the other player may continue placing his/her remaining pieces until he/she cannot do so. The game ends when both players are out of pieces or surrenders. Note that once a player surrenders, even if by mistake (when there existed valid move(s) but the player thought that there wasn't any), he/she cannot make any more moves.

You are doing a research about the strategies so you collected some end game states (the state of the grid). Can you write a program to generate a valid sequence of moves to recreate the end game state?

Input

The input consists of a $$$14 \times 14$$$ grid that consists of . (for empty cell), P for a cell that is covered by a Purple piece, or O for a cell that is covered by an Orange piece. It is guaranteed that it is a valid end game state and both players placed at least 1 piece. Which means that all rules described above are strictly followed, but it's not guaranteed that no player can make no more moves, because both players could have surrendered early by mistake.

Output

Output any sequence of moves that recreates the given end game state, starting from the empty grid. On the first line output an integer $$$N$$$ – the number of moves. The next $$$N$$$ lines describe the moves in order. A move should consist of the following the information: color num_cells row_1 column_1 [row_2 column_2]...

  • color is the color of the piece. It should be either P (for Purple) or O (for Orange)
  • num_cells is an integer between 1 and 5 inclusive that indicates the size of the piece. (number of cells that it covers)
  • After that, output the row and column number of the covered cells in any order using num_cells pairs of integers between 1 and 14.
Example
Input
..............
..............
......PPP.....
.....P.....O..
..PPPP..OO.OO.
......PO....O.
.....PPO..OO..
.....POOO.OO..
.....P...O..OO
......PPPO..O.
........PO....
........P..P..
.........PPP..
..............
Output
11
P 5 5 5 5 6 4 6 5 4 5 3
O 3 10 10 11 10 9 10
P 3 3 7 3 8 3 9
O 4 8 11 7 11 7 12 8 12
P 5 6 7 7 7 7 6 8 6 9 6
O 3 9 13 10 13 9 14
P 5 10 7 10 8 10 9 11 9 12 9
O 4 6 13 5 13 5 12 4 12
P 4 13 10 13 11 13 12 12 12
O 5 8 9 8 8 7 8 6 8 8 7
O 2 5 9 5 10