Rikka with Cake

Rikka's birthday is on June 12th. The story of this problem happens on that day.

Today is Rikka's birthday. Yuta prepares a big cake for her: the shape of this cake is a rectangular of $n$ centimeters times $m$ centimeters. With the guidance of a grimoire, Rikka is going to cut the cake.

For simplicity, Rikka firstly builds a Cartesian coordinate system on the cake: the coordinate of the left bottom corner is $(0,0)$ while that of the right top corner is $(n,m)$. There are $K$ instructions on the grimoire: The $i$th cut is a ray starting from $(x_i,y_i)$ while the direction is $D_i$. There are four possible directions: L, passes $(x_i-1,y_i)$; R, passes $(x_i+1,y_i)$; U, passes $(x_i,y_i+1)$; D, passes $(x_i,y_i-1)$.

Take advantage of the infinite power of Tyrant's Eye, Rikka finishes all the instructions quickly. Now she wants to count the number of pieces of the cake. However, since a huge number of cuts have been done, the number of pieces can be very large. Therefore, Rikka wants you to finish this task.

The first line of the input contains a single integer $T(1 \leq T \leq 100)$, the number of the test cases.

For each test case, the first line contains three positive integers $n,m,K(1 \leq n,m \leq 10^9, 1 \leq K \leq 10^5)$, which represents the shape of the cake and the number of instructions on the grimoire.

Then $K$ lines follow, the $i$th line contains two integers $x_i,y_i(1 \leq x_i < n, 1 \leq y_i <m)$ and a char $D_i \in \{$'L','R','U','D'$\}$, which describes the $i$th cut.

The input guarantees that there are no more than $5$ test cases with $K > 1000$, and no two cuts share the same $x$ coordinate or $y$ coordinate, i.e., $\forall 1 \leq i < j \leq K$, $x_i \neq x_j$ and $y_i \neq y_j$.

For each test case, output a single line with a single integer, the number of pieces of the cake.

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

3
5

2019 Multi-University Training Contest 9