Problem Description

Teo’s balcony is a rectangular platform with length $n+1$ and width $m+1$. There are $2k$ colored lights on it. The color of each light is represented by a number from $1 \sim k$. For each color, there are exactly $2$ lights, and all their coordinates are positive integers.

Teo considers a region on the balcony to be good if and only if:

• This region is a rectangle, and all its sides are parallel to the sides of the balcony.

• For the two lights of each color, either both are inside the region, or both are outside the region.

• The coordinates of the top-left corner and the bottom-right corner of the region are both integers.

• The length and width of the region are both at least $2$.

Now Teo wants you to find how many good regions there are on his balcony.

Note: the bottom-left corner is $(0,0)$, and the top-right corner is $(n,m)$.

Input Format

The first line contains three integers $n$, $m$, $k$ ($1\le n\le150,1\le m\le1000,0\le k\le200000$), representing the length and width of the balcony, and the number of light colors.

The next $k$ lines each contain four integers $x_1$, $y_1$, $x_2$, $y_2$. The $i$-th line gives the coordinates of the two lights of color $i$.

Output Format

One line containing one integer, the number of good regions.

2 2 1
0 0 1 2

3

3 3 0

36

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

7

Hint

The full score for this problem is $110$ points.

Translated by ChatGPT 5