There is an $n$ by $m$ chessboard with $n\times m$ squares in total. Rows and columns are numbered starting from $1$, and the coordinates of the square in the $i$-th column and $j$-th row are denoted as $(i,j)$. Initially, all squares are white. Now, you need to perform $q$ coloring operations on this chessboard.

There are three types of coloring operations:

• Color a horizontal line black. Specifically, given two squares $(x_1,y_1)$ and $(x_2,y_2)$ with $y_1=y_2$, color all squares between (including) these two squares black.
• Color a vertical line black. Specifically, given two squares $(x_1,y_1)$ and $(x_2,y_2)$ with $x_1=x_2$, color all squares between (including) these two squares black.
• Color a diagonal line black. Specifically, given two squares $(x_1,y_1)$ and $(x_2,y_2)$ with $x_2-x_1=y_2-y_1$ and $x_1\le x_2$, color all squares with coordinates $(x_1+i,y_1+i)$ on the diagonal between these two squares, where $0\le i\le x_2-x_1$. The number of times this type of coloring operation occurs is no more than $5$.

Now you want to know how many black squares there are on the chessboard after performing $q$ coloring operations.

Input Specification

The first line of input contains an integer $c$, which represents the test case number. If $c=0$, it means that this test case is a sample test.

The second line of input contains three positive integers $n$, $m$, and $q$, which respectively represent the number of columns, rows, and the number of coloring operations on the chessboard.

Then $q$ lines follow, each line containing five positive integers $t,x_1,y_1,x_2,y_2$. Among them, $t=1$ represents the first type of coloring operation, $t=2$ represents the second type of coloring operation, and $t=3$ represents the third type of coloring operation. $x_1,y_1,x_2,y_2$ represent the four parameters of the coloring operation.

Output Specification

Output a line containing an integer, representing the number of black squares on the chessboard that have been colored.

Sample Input 1

0
5 5 3
1 1 3 5 3
2 3 1 3 5
3 1 1 5 5

Sample Output 1

13

Explanation of Sample Output 1

In this sample test, we performed a total of three coloring operations, as shown in the following figure. The state of the chessboard after each of the three operations are given in the order from left to right.

After the first operation, squares $(1,3)$, $(2,3)$, $(3,3)$, $(4,3)$, $(5,3)$ are colored black.

After the second operation, squares $(3,1)$, $(3,2)$, $(3,3)$, $(3,4)$, $(3,5)$ are colored black.

After the third operation, $(1,1)$, $(2,2)$, $(3,3)$, $(4,4)$, $(5,5)$ are colored black.

After all three coloring operations, a total of $13$ squares are colored black.

Additional Samples

Sample inputs and outputs can be found here.

• Sample 2 (ex_color2.in and ex_color2.ans) corresponds to test cases 1-5.
• Sample 3 (ex_color3.in and ex_color3.ans) corresponds to test cases 6-9.
• Sample 4 (ex_color4.in and ex_color4.ans) corresponds to test cases 10-13.
• Sample 5 (ex_color5.in and ex_color5.ans) corresponds to test cases 14-17.
• Sample 6 (ex_color6.in and ex_color6.ans) corresponds to test cases 18-19.
• Sample 7 (ex_color7.in and ex_color7.ans) corresponds to test case 20.

Constraints

For all test data, it is guaranteed that: $1\le n,m\le {10}^9,1\le q\le {10}^5,1\le x_1,x_2\le n,1\le y_1,y_2\le m$, and there are at most $5$ operations of the third type.

Test ID	$n,m\le$	$q\le$	Additional Constraints
$1\sim 5$	$300$	$300$	None
$6\sim 9$	${10}^5$	$2000$
$10\sim 13$		${10}^5$	A
$14\sim 17$			B
$18\sim 19$			None
$20$	${10}^9$

Additional Constraint A: It is guaranteed that there is only the first type of coloring operation.

Additional Constraint B: It is guaranteed that there are only the first and second type of coloring operation.