One day, Vlad and John thought about expanding the concept of Tic Tac Toe. Instead of adding X and 0 in the 9 squares of the 3x3 board, they thought of using the edges of the board.
At the beginning, only 9 dots exist, arranged into an array with 3 dots per line and 3 lines. Only pairs of points that form edges helping at the reconstruction of the original Tic Tac Toe board can be united. However, at one time, one player can draw only one edge. The players move alternatively.
There are 9 little squares that are placed inside this board, each one of it having 4 edges. When a player draws the 4th edge of one of those squares, he becomes the owner of the square, and he has the right to one additional move.
Given an existing configuration of the board, specify what happens if the current player plays optimal.
On the first line of the input file there are 4 numbers separated by space, P, A, B, N.
P is 1 if the first player must move, or 2 if the second player must move. The A and B numbers represent how many squares are owned by each player until now. N represents the number of moves made until now.
The N lines that follow describe the moves made. The columns of the board are identified as 1, 2, 3, and the lines as A, B, C, in that order. Dots are identified as an association of a letter and a digit (for example: A1, B3, C2). One move is represented as an association of two points that are been united. For example, A1B1 represents a vertical line made from point A1 to the point B1.
The minimal number of squares that the current player will certainly own at the end of the game, if he plays optimal.
2 0 0 15 A1B1 B1C1 A2B2 B2C2 A2A3 C4D4 C1D1 D1D2 D2D3 D3C3 A3A4 A4B4 C3C4 B2B3 B3C3
9