Problem Description

There is a chessboard with $n$ columns and $m$ rows, with a total of $n \times m$ cells. We agree that both rows and columns are numbered starting from $1$, and the cell in column $i$ and row $j$ has coordinates $(i, j)$. Initially, all cells are white. Now you need to perform $q$ coloring operations on this chessboard.

There are three types of coloring operations:

1. Color a horizontal segment black. Specifically, given two cells $(x_1, y_1)$ and $(x_2, y_2)$, with $x_1 \le x_2$ and $y_1 = y_2$, color all cells between these two cells (including them) black.
2. Color a vertical segment black. Specifically, given two cells $(x_1, y_1)$ and $(x_2, y_2)$, with $x_1 = x_2$ and $y_1 \le y_2$, color all cells between these two cells (including them) black.
3. Color a diagonal segment black. Specifically, given two cells $(x_1, y_1)$ and $(x_2, y_2)$, with $x_1 \le x_2$ and $x_2 - x_1 = y_2 - y_1$, color all cells on the diagonal between them of the form $(x_1 + i, y_1 + i)$ ($0 \le i \le x_2 - x_1$) black. The number of times this type of coloring operation occurs does not exceed $5$.

Now you want to know: after the $q$ coloring operations, how many black cells are on the chessboard.

Input Format

The first line contains an integer $c$, which indicates the test point index. $c = 0$ means this test point is a sample.

The second line contains three positive integers $n, m, q$, representing the number of columns, the number of rows, and the number of coloring operations.

The next $q$ lines each contain five positive integers $t, x_1, y_1, x_2, y_2$. Here, $t = 1$ means the first type of coloring operation, $t = 2$ means the second type, and $t = 3$ means the third type. $x_1, y_1, x_2, y_2$ are the four parameters of the coloring operation.

Output Format

Output one line containing an integer, representing the number of cells colored black on the chessboard.

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

13

见附件中的 color/color2.in。

见附件中的 color/color2.ans。

见附件中的 color/color3.in。

见附件中的 color/color3.ans。

见附件中的 color/color4.in。

见附件中的 color/color4.ans。

见附件中的 color/color5.in。

见附件中的 color/color5.ans。

见附件中的 color/color6.in。

见附件中的 color/color6.ans。

见附件中的 color/color7.in。

见附件中的 color/color7.ans。

Hint

[Sample Explanation #1]

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

In the first operation, we colored $(1, 3), (2, 3), (3, 3), (4, 3), (5, 3)$ black.

In the second operation, we colored $(3, 1), (3, 2), (3, 3), (3, 4), (3, 5)$ black.

In the third operation, we colored $(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)$ black.

[Sample #2]

This sample satisfies the constraints for test points $1 \sim 5$.

[Sample #3]

This sample satisfies the constraints for test points $6 \sim 9$.

[Sample #4]

This sample satisfies the constraints for test points $10 \sim 13$.

[Sample #5]

This sample satisfies the constraints for test points $14 \sim 17$.

[Sample #6]

This sample satisfies the constraints for test points $18 \sim 19$.

[Sample #7]

This sample satisfies the constraints for test point $20$.

[Constraints]

For all testdata, 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.

::cute-table{tuack}

Special property A: it is guaranteed that there are only the first type of coloring operations.

Special property B: it is guaranteed that there are only the first and second types of coloring operations.

Update on 2023-08-04: A set of Hack testdata was updated, where $c = 0$.

Translated by ChatGPT 5