Chuan the Qi Shen (棋神) has decided to participate in the Chessboard-Model Imaging (CMI) competition! Basically, he has to submit an image of size w x h made of only the colors black and white. As Chuan is lazy, he opens up Paint and randomly draws in M black rectangles.
Now, he is happy with the end-product and has decided to submit the image. However, he is curious, how many separate white regions are there in the image?
Input
The first line contains two space-separated integers
w and
h (1 ≤
w,
h ≤ 1,000,000).
The second line contains one integer
M (1 ≤
M ≤ 1,000).
The next
M lines contain four integers
x1,
y1,
x2 and
y2 (0 ≤
x1 <
x2 ≤
w, 0 ≤
y1 <
y2 ≤
h).
Note that the bottom left corner is (0,0) and the top right corner is (
w,
h).
Output
Output the number of separate white regions.
Grading
For 30% of test data,
w,
h and
n ≤ 100.
Sample Input 1
15 6
10
1 4 5 6
2 1 4 5
1 0 5 1
6 1 7 5
7 5 9 6
7 0 9 2
9 1 10 5
11 0 14 1
12 1 13 5
11 5 14 6
Sample Output 1
5
Sample Input 2
8 8
3
0 0 4 4
4 4 8 8
1 1 2 2
Sample Output 2
2