Problem Description

There is a chessboard with \( n \) columns and \( m \) rows, totaling \( n \times m \) squares. Rows and columns are numbered starting from 1, and the square located in the \( i \)-th column and \( j \)-th row is denoted as \( (i, j) \). Initially, all squares are white. You are to perform \( q \) coloring operations on this chessboard.

There are three types of coloring operations:

1. Color a horizontal line black. Specifically, given two squares \( (x_1, y_1) \) and \( (x_2, y_2) \), with \( x_1 \le x_2 \) and \( y_1 = y_2 \), color all squares between (including) these two squares black.
2. Color a vertical line black. Specifically, given two squares \( (x_1, y_1) \) and \( (x_2, y_2) \), with \( x_1 = x_2 \) and \( y_1 \le y_2 \), color all squares between (including) these two squares black.
3. Color a diagonal line black. Specifically, given two squares \( (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 squares on the diagonal line of the form \( (x_1 + i, y_1 + i) \) (where \( 0 \le i \le x_2 - x_1 \)) black. This type of operation occurs at most 5 times.

You want to know how many squares on the chessboard are black after \( q \) coloring operations.

Input Format

The first line of input contains an integer \( c \), indicating the test point number. \( c = 0 \) means this is a sample test case.

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

The next \( q \) lines each contain five positive integers \( t, x_1, y_1, x_2, y_2 \). \( t = 1 \) indicates the first type of coloring operation, \( t = 2 \) indicates the second type, and \( t = 3 \) indicates the third type. \( x_1, y_1, x_2, y_2 \) are the parameters for the coloring operation.

Output Format

Output a single line containing an integer, representing the number of black squares on the chessboard.

Sample Input and Output

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

Sample Input #2

See the attached file color/color2.in.

Sample Output #2

See the attached file color/color2.ans.

Sample Input #3

See the attached file color/color3.in.

Sample Output #3

See the attached file color/color3.ans.

Sample Input #4

See the attached file color/color4.in.

Sample Output #4

See the attached file color/color4.ans.

Sample Input #5

See the attached file color/color5.in.

Sample Output #5

See the attached file color/color5.ans.

Sample Input #6

See the attached file color/color6.in.

Sample Output #6

See the attached file color/color6.ans.

Sample Input #7

See the attached file color/color7.in.

Sample Output #7

See the attached file color/color7.ans.

Notes/Hints

[Sample Explanation #1]

In this sample, we perform three coloring operations as shown in the following diagram:

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

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

During the third operation, squares \( (1, 1), (2, 2), (3, 3), (4, 4), (5, 5) \) are colored black.

[Data Range]

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 third type coloring operations.

Special Condition A: Only the first type of coloring operation is guaranteed.

Special Condition B: Only the first and second types of coloring operations are guaranteed.

Update on 2023-08-04: Added a new Hack data set where \( c = 0 \).

见题面 Input 部分

见题面 Output 部分