Chess Piece Removal

The Chess Piece Removal game is played on an \(r \times c\) board. Each cell of the board is either empty (denoted by .) or contains a colored piece. Each color appears exactly twice on the board.

In one move, a player selects an empty cell \((x,y)\) (1-indexed) and chooses two distinct directions from the set \(\{U, D, L, R\}\) (representing Up, Down, Left, Right). For each chosen direction, starting from \((x,y)\) and moving in that direction, the first encountered non-empty cell is considered. If both chosen directions yield a piece and both pieces have the same color, then these two pieces are removed (i.e. the cells become empty). Otherwise, the move is invalid and the board remains unchanged.

You are given a board and a sequence of moves performed by a player. Your tasks are:

1. Determine how many pieces the player successfully removed by following the given moves.
2. Compute the maximum number of pieces that can be removed from the board through an optimal sequence of valid moves.

Note: All formulas are in \(\LaTeX\) format.

inputFormat

The input is given as follows:

• The first line contains two integers \(r\) and \(c\) (number of rows and columns).
• The next \(r\) lines each contain a string of length \(c\). Each character is either . (an empty cell) or an uppercase letter representing a colored piece.
• The next line contains an integer \(n\), the number of moves performed by the player.
• Each of the following \(n\) lines contains: \(x\), \(y\), \(d_1\), and \(d_2\), where \(x\) and \(y\) (1-indexed) denote the selected empty cell, and \(d_1\) and \(d_2\) are two distinct directions from the set {U, D, L, R}.

For example, a test case might be:

3 3
.A.
B.B
.A.
3
2 1 R D
1 1 D R
3 3 U L

outputFormat

Output two integers separated by a space:

• The first integer is the number of pieces removed by the player's moves.
• The second integer is the maximum number of pieces that can be removed from the board by an optimal sequence of moves.

For the sample input above, the correct output would be:

0 4

sample

3 3
.A.
B.B
.A.
3
2 1 R D
1 1 D R
3 3 U L

0 4