P9478 [NOI2023] Grid Coloring.

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.

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 one line containing an integer, representing the number of cells colored black on the chessboard.

**[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} |Test Point Index|$n, m \le$|$q \le$|Special Property| |:-:|:-:|:-:|:-:| |$1 \sim 5$|$300$|$300$|None| |$6 \sim 9$|$10 ^ 5$|$2,000$|None| |$10 \sim 13$|$10 ^ 5$|$10 ^ 5$|A| |$14 \sim 17$|$10 ^ 5$|$10 ^ 5$|B| |$18 \sim 19$|$10 ^ 5$|$10 ^ 5$|None| |$20$|$10 ^ 9$|$10 ^ 5$|None| 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