说明

JOI 君喜欢做纸艺。今天 JOI 君也打算制作一个纸艺作品。首先，JOI 君按照设计图在一张长方形纸上印刷了 $N$ 条切割线。每条切割线都是与纸的纵边或横边平行的线段。

通过切割纸张得到的所有部分都将作为作品中的某些部件使用。显然，部件数量多的作品制作起来更麻烦。JOI 君想知道，如果按照所有切割线切割纸张，纸张会被分成多少部分。

任务

给定纸张的大小和 $N$ 条切割线的信息。编写程序，求出按照这些切割线切割后，纸张会被分成多少部分。

输入格式

从标准输入读取以下数据。

• 第 1 行包含以空格分隔的整数 $W, H, N$。$W$ 表示纸张横向边的长度，$H$ 表示纸张纵向边的长度，$N$ 表示切割线的数量。纸张的左下、右下、左上、右上顶点分别用坐标 $(0,0), (W,0), (0,H), (W,H)$ 表示。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含以空格分隔的整数 $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$)。表示第 $i$ 条切割线是连接 $(A_i, B_i)$ 和 $(C_i, D_i)$ 的线段。这条线段与纸的某条边平行。也就是说，$A_i = C_i$ 与 $B_i = D_i$ 这两个条件恰好有一个成立。此外，任意一条切割线与其平行的其他切割线没有公共点，任意一条切割线与其平行的纸的边也没有公共点。

输出格式

向标准输出输出一行，包含一个整数，表示纸张被分成的部分数量。

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

提示

样例解释 1

对于此输入，切割线如下图所示。

:::align{center} :::

因此，切割线将纸张分成了 $4$ 个部分。注意，此输入满足子任务 4 的条件。

样例解释 2

对于此输入，切割线如下图所示。

:::align{center} :::

因此，切割线将纸张分成了 $5$ 个部分。注意，此输入不满足子任务 4 的条件。

数据范围

所有输入数据满足以下条件。

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

子任务

子任务 1 [5 分]

满足以下条件。

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

子任务 2 [5 分]

满足以下条件。

• $N \le 1000$

子任务 3 [20 分]

存在公共点的不同切割线对的数量不超过 $100000$。

子任务 4 [20 分]

从任意一条切割线上的任意一点出发，都可以沿着若干条切割线到达纸的某条边上的点。

子任务 5 [50 分]

没有额外限制。

翻译由 DeepSeek V3.2 完成