JOI-kun is a fan of papercraft. Today, he is planning to make a papercraft project. First, JOI-kun printed $N$ cutting lines on a rectangular sheet of paper according to his blueprint. Each cutting line is a line segment parallel to either the vertical or horizontal edge of the paper. All parts created by cutting the paper will be used as some kind of component in the project. Naturally, a project with many parts is difficult to produce. JOI-kun wants to know how many pieces the paper will be divided into when he cuts the paper along all the cutting lines.

Description

Given the size of the paper and information about the $N$ cutting lines, write a program to determine how many pieces the paper is divided into when cut along these lines.

Input

Read the following data from standard input:

• The first line contains three integers $W, H, 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 bottom-left, bottom-right, top-left, and top-right corners of the paper are represented by the coordinates $(0, 0), (W, 0), (0, H), (W, H)$, respectively.
• The following $N$ lines, the $i$-th line ($1 \le i \le N$), contains four 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$) separated by spaces. This indicates that the $i$-th cutting line is a line segment connecting $(A_i, B_i)$ and $(C_i, D_i)$. This line segment is parallel to one of the edges of the paper. That is, exactly one of $A_i = C_i$ or $B_i = D_i$ holds. Furthermore, no two cutting lines that are parallel to each other share any common points, and no cutting line shares any common points with an edge of the paper that is parallel to it.

Output

Output a single integer representing the number of pieces the paper is divided into on a single line to standard output.

Constraints

All input data satisfies the following conditions:

• $1 \le W \le 1\,000\,000\,000$
• $1 \le H \le 1\,000\,000\,000$
• $1 \le N \le 100\,000$

Subtasks

Subtask 1 [5 points]

The following conditions are satisfied: $W \le 1\,000$ $H \le 1\,000$ * $N \le 1\,000$

Subtask 2 [5 points]

The following condition is satisfied: * $N \le 1\,000$

Subtask 3 [20 points]

The number of pairs of distinct cutting lines that share a common point is $100\,000$ or less.

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 following a sequence of cutting lines.

Subtask 5 [50 points]

There are no additional constraints.

Examples

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

Output 1

4

Note 1

In this case, the cutting lines are as shown in the figure below.

Thus, the paper is divided into 4 pieces by the cutting lines. Note that this input satisfies the conditions of Subtask 4.

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

Output 2

5

Note 2

In this case, the cutting lines are as shown in the figure below.

Thus, the paper is divided into 5 pieces by the cutting lines. Note that this input does not satisfy the conditions of Subtask 4.