Problem Description

JOI is passionate about paper crafting. Today, he is trying to create a paper craft piece.

First, JOI printed \( N \) cutting lines on a rectangular sheet of paper according to the blueprint. Each cutting line is a segment parallel to the vertical or horizontal edges of the paper. All parts of the paper that are cut out will be used as components in the piece. Naturally, a piece with more components is more difficult to make. JOI wants to know how many parts the paper will be divided into when all the cutting lines are followed.

Input Format

Read the following data from standard input:

• The first line contains integers \( W \), \( H \), and \( N \) separated by spaces. \( W \) represents the length of the horizontal edge of the paper, \( H \) represents the length of the vertical edge of the paper, and \( N \) represents the number of cutting lines. The coordinates of the bottom-left, bottom-right, top-left, and top-right corners of the paper are \( (0, 0) \), \( (W, 0) \), \( (0, H) \), and \( (W, H) \), respectively.
• The next \( N \) lines contain integers \( A_i \), \( B_i \), \( C_i \), and \( D_i \) (where \( 0 \leq A_i \leq C_i \leq W \) and \( 0 \leq B_i \leq D_i \leq H \)) separated by spaces. This represents the \( i \)-th cutting line connecting points \( (A_i, B_i) \) and \( (C_i, D_i) \). This segment is parallel to one of the edges of the paper, meaning exactly one of \( A_i = C_i \) or \( B_i = D_i \) holds. No cutting line will have a common point with another cutting line parallel to it, nor will it have a common point with an edge of the paper parallel to it.

Output Format

Output a single integer on standard output, representing the number of parts the paper will be divided into.

Sample Input and Output

Sample Input #1

10 10 5
6 0 6 7
0 6 7 6
2 3 9 3
2 3 2 10
1 9 8 9

Sample Output #1

4

Sample Input #2

13 7 28
1 1 4 1
1 1 1 3
2 2 3 2
2 2 2 3
1 3 2 3
3 2 3 6
4 1 4 6
3 6 4 6
5 1 8 1
5 1 5 6
6 2 7 2
6 2 6 5
7 2 7 5
6 5 7 5
8 1 8 6
5 6 8 6
9 1 12 1
9 1 9 2
9 2 10 2
12 1 12 2
11 2 12 2
10 2 10 5
9 5 10 5
9 5 9 6
11 2 11 5
11 5 12 5
12 5 12 6
9 6 12 6

Sample Output #2

5

Notes/Hints

Task

Given the size of the paper and the information about \( N \) cutting lines, create a program that determines how many parts the paper will be divided into when cut according to these lines.

Constraints

All input data satisfies the following conditions:

• \( 1 \leq W \leq 1,000,000,000 \).
• \( 1 \leq H \leq 1,000,000,000 \).
• \( 1 \leq N \leq 100,000 \).

Subtasks

Subtask 1 \[5 points\]

Satisfies the following conditions:

• \( W \leq 1,000 \).
• \( H \leq 1,000 \).
• \( N \leq 1,000 \).

Subtask 2 \[5 points\]

Satisfies the following conditions:

• \( N \leq 1,000 \).

Subtask 3 \[20 points\]

The number of pairs of different cutting lines that have a common point is at most \( 100,000 \).

Subtask 4 \[20 points\]

From any point on a cutting line, it is possible to reach a point on an edge of the paper by traversing some cutting lines.

Subtask 5 \[50 points\]

No additional constraints.

Sample Explanation 1

In this input, the cutting lines are as shown in the figure below. Thus, the paper is divided into 4 parts by the cutting lines. Note that this input satisfies the conditions of Subtask 4.

Sample Explanation 2

In this input, the cutting lines are as shown in the figure below. Thus, the paper is divided into 5 parts by the cutting lines. Note that this input does not satisfy the conditions of Subtask 4.

见题面 Input 部分

见题面 Output 部分