Description

Remove Pieces is an interesting game. The game is played on an $r \times c$ board. Each cell of the board is either empty or contains a piece of some color. Each color appears exactly twice. In each round, the player can choose an empty cell $(x, y)$ and choose two directions among up, down, left, and right. If, in each of the two chosen directions, there exists a cell containing a piece, and the first piece encountered along each direction has the same color, then we take away those two pieces, and call this a legal move. Otherwise, the move is illegal and the game will not process this move. The goal is to remove as many pieces as possible.

Given such a game and a person's sequence of moves, you need to:

1. State how many pieces this person can remove.
2. Provide a sequence of moves that removes the maximum number of pieces.

Input Format

The first line gives the integers $r$, $c$.

The second line gives the integer $n$, the number of different colors.

The next $n$ lines, the $i$-th line contains four integers $a_i, b_i, c_i, d_i$, meaning that the two cells of color $i$ are $(a_i, b_i),\ (c_i, d_i)$.

Then an integer $m$ follows, the number of this person’s moves. The next $m$ lines each contain two integers and two letters, representing the chosen cell and the two directions. We use $\texttt{UDLR}$ to denote up, down, left, and right, respectively.

Output Format

The first line outputs how many pieces this person can remove.

The second line contains an integer $k$, the number of moves in your sequence.

The next $k$ lines each contain two integers and two letters, representing your chosen cell and the two directions.

4 4
4
1 1 1 4
1 2 3 4
1 3 3 2
4 1 2 3
6
2 3 U R
2 1 D R
2 2 L R
2 4 L D
3 1 L R
3 3 L U

2
4
4 3 L U
3 3 L U
3 2 R U
1 2 L R

Hint

For all testdata, $1 \leq r, c, n \leq 10^5$, and it is guaranteed that in the answer the number of operations satisfies $0 \leq k \leq 10^6$.

Translated by ChatGPT 5