Problem Description

JOI likes paper craft. Today, JOI is also going to make a paper craft work. First, following the design, JOI prints $N$ cutting lines on a rectangular sheet of paper. Each cutting line is a line segment parallel to either the vertical sides or the horizontal sides of the paper.

All pieces obtained by cutting the paper will be used as parts of the work. Obviously, a work with more parts is harder to make. JOI wants to know: if the paper is cut along all the cutting lines, into how many pieces will it be divided?

Task

Given the size of the paper and the information of $N$ cutting lines, write a program to compute how many pieces the paper will be divided into after cutting along these lines.

Input Format

Read the following data from standard input.

• Line 1 contains space-separated integers $W, H, N$. $W$ is the length of the horizontal side of the paper, $H$ is the length of the vertical side, and $N$ is the number of cutting lines. The bottom-left, bottom-right, top-left, and top-right vertices of the paper are represented by coordinates $(0,0)$, $(W,0)$, $(0,H)$, $(W,H)$, respectively.
• In each of the next $N$ lines, line $i$ ($1 \le i \le N$) contains space-separated integers $A_i, B_i, C_i, D_i$ ($0 \le A_i \le C_i \le W$, $0 \le B_i \le D_i \le H$). This means the $i$-th cutting line is the segment connecting $(A_i, B_i)$ and $(C_i, D_i)$. This segment is parallel to one side of the paper. That is, exactly one of the two conditions $A_i = C_i$ and $B_i = D_i$ holds. In addition, any cutting line has no common point with any other cutting line parallel to it, and any cutting line also has no common point with the side of the paper parallel to it.

Output Format

Output one line to standard output containing one integer, representing the number of pieces the paper is divided into.

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

4

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

5

Hint

Sample Explanation 1

For this input, the cutting lines are as shown in the figure below.

:::align{center} :::

Therefore, the cutting lines divide the paper into $4$ pieces. Note that this input satisfies the conditions of Subtask 4.

Sample Explanation 2

For this input, the cutting lines are as shown in the figure below.

:::align{center} :::

Therefore, the cutting lines divide the paper into $5$ pieces. Note that this input does not satisfy the conditions of Subtask 4.

Constraints

All input data satisfy the following conditions.

• $1 \le W \le 1000000000$
• $1 \le H \le 1000000000$
• $1 \le N \le 100000$

Subtasks

Subtask 1 [5 points]

Satisfies the following conditions.

• $W \le 1000$
• $H \le 1000$
• $N \le 1000$

Subtask 2 [5 points]

Satisfies the following condition.

• $N \le 1000$

Subtask 3 [20 points]

The number of pairs of different cutting lines that have a common point does not exceed $100000$.

Subtask 4 [20 points]

Starting from any point on any cutting line, it is possible to reach a point on some side of the paper by moving along several cutting lines.

Subtask 5 [50 points]

No additional restrictions.

Translated by DeepSeek V3.2.

Translated by ChatGPT 5