There is a grid with $n$ columns and $m$ rows, containing a total of $n \times m$ cells. We define the rows and columns as being 1-indexed, and the cell in the $i$-th column and $j$-th row is denoted by $(i, j)$. Initially, all cells are white. You are to perform $q$ coloring operations on this grid.

There are three types of coloring operations:

1. Color a horizontal line black. Specifically, given two cells $(x_1, y_1)$ and $(x_2, y_2)$, where $y_1 = y_2$, color all cells between these two cells (inclusive) black.
2. Color a vertical line black. Specifically, given two cells $(x_1, y_1)$ and $(x_2, y_2)$, where $x_1 = x_2$, color all cells between these two cells (inclusive) black.
3. Color a diagonal line black. Specifically, given two cells $(x_1, y_1)$ and $(x_2, y_2)$, where $x_2 - x_1 = y_2 - y_1$ ($x_1 \le x_2$), color all cells on the diagonal between these two cells of the form $(x_1 + i, y_1 + i)$ ($0 \le i \le x_2 - x_1$) black. This type of coloring operation occurs at most 5 times.

After $q$ operations, you want to know how many black cells are on the grid.

Input

The first line contains an integer $c$, representing the test case number. $c = 0$ indicates that the test case is a sample. The second line contains three positive integers $n, m, q$, representing the number of columns, rows, and coloring operations, respectively. The next $q$ lines each contain five positive integers $t, x_1, y_1, x_2, y_2$. Here, $t = 1$ represents the first type of operation, $t = 2$ represents the second type, and $t = 3$ represents the third type. $x_1, y_1, x_2, y_2$ are the four parameters for the coloring operation.

Output

Output a single integer representing the number of cells colored black on the grid.

Examples

Input 1

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

Output 1

13

Note

In this sample, we performed a total of three coloring operations, as shown in the figure below.

Figure 1: Sample image

The first operation colors $(1, 3), (2, 3), (3, 3), (4, 3), (5, 3)$ black. The second operation colors $(3, 1), (3, 2), (3, 3), (3, 4), (3, 5)$ black. The third operation colors $(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)$ black. After the three operations, a total of 13 cells are colored black.

Examples 2-7

The sample files color/color2.in through color/color7.in and their corresponding .ans files are provided in the contestant directory. These samples satisfy the constraints for the respective test cases as indicated in the problem description.

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.

Special Property A: Guaranteed to only have the first type of coloring operation. Special Property B: Guaranteed to only have the first and second types of coloring operations.