2760 「JOI 2014 Final」裁剪线

译自 JOI 2014 Final T5「切り取り線」

JOI 君对剪纸很感兴趣。今天 JOI 君也准备做剪纸。

首先，JOI 君根据设计图在一张长方形的纸上画了 $N$ 条裁剪线。每条裁剪线都是一条与纸的长或宽平行的线段。

从纸上切下来的所有部分都会被用作作品中的部件。可以理解的是，部件数量越多的作品制作起来越困难。JOI 君想知道，当他沿着每一条裁剪线把纸剪开之后，这张纸被分成了多少个部分。

任务

给出纸的大小和 $N$ 条裁剪线的相关信息，请求出沿着这些裁剪线剪开之后，这张纸被分成了多少个部分。

第一行包含三个以空格分开的整数 $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}$ 中恰有一个成立。而且，相互平行的裁剪线之间没有公共点，裁剪线和与之平行的边之间也没有公共点。

输出到标准输出，表示纸被分成的部分个数。

输入数据对应裁剪线位置如下图：

因此，纸会被裁剪线划分成 4 个部分。另外，本组输入数据满足子任务 4 的条件。

输入数据对应裁剪线位置如下图：

因此，纸会被裁剪线划分成 5 个部分。另外，本组输入数据并不满足子任务 4 的条件。

全部的输入数据满足以下条件：

• $1\le W\le 10^{9}$
• $1\le H\le 10^{9}$
• $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 分]

没有额外限制。