30419번 - Square Coloring 다국어

문제

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 \leq x_2,ドル color all squares with coordinates $(x_1+i, y_1+i)$ on the diagonal between these two squares, where 0ドル \leq i \leq 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.

입력

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 a line containing an integer, representing the number of black squares on the chessboard that have been colored.

제한

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

힌트

추가 예제

samples.zip ​​​​​​​