Number of Paint Colors

Time limit2sMemory limit128 MB

Summary

Count connected regions of a rectangle cut by up to 1000 axis-aligned masking tape rectangles, where regions sharing only a corner stay separate.

Level: Medium7 of 10
Topics: Combinatorics, Geometry, Union-find
Solved: No attempts yet

Problem

To advertise an informatics olympiad, you want to make a signboard by painting a rectangular plywood board. On the parts of the board that should stay unpainted, several rectangular strips of masking tape have already been applied. You therefore decide to paint each region separated by the masking tape with a different color. For example, the board in Figure 5-1 uses 5 colors of paint.

Figure 5-1 An example signboard

Two regions that share a boundary segment of positive length are considered to be connected into one region and are painted the same color, while two regions that touch only at a single corner point are counted as different regions.

Given the positions where the masking tape is applied, write a program that computes the number of paint colors used. It is guaranteed that the whole board is never completely covered by masking tape, and every side of every masking tape is parallel to one of the sides of the board.

Input

The first line contains the width $w$ (an integer with $1 \le w \le 1000000$ ) and the height $h$ (an integer with $1 \le h \le 1000000$ ) of the plywood board, in this order, separated by a space.

The second line contains the number of masking tapes $n$ (an integer with $1 \le n \le 1000$ ). Each of the following $n$ lines, the $i$ -th line ( $1 \le i \le n$ ), contains the bottom-left coordinate $(x_1, y_1)$ and the top-right coordinate $(x_2, y_2)$ of the $i$ -th masking tape, given as $x_1\ y_1\ x_2\ y_2$ (integers with $0 \le x_1 < x_2 \le w$ and $0 \le y_1 < y_2 \le h$ ), separated by spaces.

The bottom-left corner of the board is at $(0, 0)$ and the top-right corner is at $(w, h)$ .

Output

Print the number of paint colors used on a single line.

Hint

The following figure shows the input example corresponding to the signboard in Figure 5-1.

Figure 5-2 Input example for the signboard in Figure 5-1

Examples3

Example 1

Input

Expected output

Example 2
Input
```
3 1
1
1 0 2 1
```
Expected output
```
2
```
Example 3
Input
```
3 3
2
0 1 3 2
1 0 2 3
```
Expected output
```
4
```