Eliminating Chess Pieces is an interesting game. The game is played on an $r \times c$ board. Each cell on the board is either empty or contains a chess piece of a certain color. There are exactly two pieces of each color. In each round, a player can choose an empty cell $(x, y)$ and two directions out of the four cardinal directions (up, down, left, right). If there are pieces in both chosen directions, and the first piece encountered in each of these two directions has the same color, then we remove these two pieces; this is called a legal operation. Otherwise, the operation is illegal, and the game will not process it. The goal of the game is to eliminate as many pieces as possible.

Given such a game and a sequence of moves made by a person, you need to: Determine how many pieces this person can eliminate. Provide a sequence of moves that eliminates the maximum possible number of pieces.

Input

The first line contains two integers $r, c$. The second line contains an integer $n$, representing the number of different colors. The next $n$ lines each contain four integers $a[i], b[i], c[i], d[i]$, representing that the two pieces of color $i$ are located at $(a[i], b[i])$ and $(c[i], d[i])$. Then follows an integer $m$, representing the number of moves made by the person. The next $m$ lines each contain two integers and two characters, representing the chosen cell and the two directions. We use "U", "D", "L", "R" to represent up, down, left, and right, respectively.

Output

The first line should output how many pieces the person can eliminate. The second line should contain an integer $k$ ($0 \le k \le 10^6$), representing the number of moves in your proposed sequence. The next $k$ lines should each contain two integers and two characters, representing the cell and the two directions you choose.

Constraints

• For 10% of the data, $1 \le r, c, n, m \le 10$.
• For 20% of the data, $1 \le r, c, n, m \le 100$.
• For 40% of the data, $1 \le n, m \le 100$.
• For 50% of the data, $1 \le n, m \le 1000$.
• For 60% of the data, $1 \le n \le 1000$.
• Additionally, for 10% of the data, $c=1$.
• For 100% of the data, $1 \le r, c, n, m \le 10^5$.

Examples

Input 1

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

Output 1

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