配点: 100 点
JOI 君从事纸工艺。今天 JOI 君也打算制作纸工艺作品。
首先,JOI 君按照设计图 1 张长方形的纸上 N 打印书的裁切线。每条裁切线都是与纸张的纵边或横边平行的线段。切割纸张所得到的所有部分都将作为作品中的某些部件使用。理所当然,部件数量多的作品制作起来也更费力。JOI君想知道,如果按照所有裁切线将纸切开,纸会被分成多少个部分。
課題
给出纸的大小,N 以及书的裁切线信息。根据这些裁切线切割纸张时,编写程序求出纸会被分成多少个部分。
入力
从标准输入读取以下数据。
- 1 行表示整数 W, H, N 使用空格作为分隔符。W 表示纸的横边长度,H 表示纸的纵边长度,N 表示裁切线的数量。纸的左下角、右下角、左上角和右上角分别用坐标 (0, 0), (W, 0), (0, H), (W, H) 表示。
- 继续 N 行 i 行目 (1 \leqq i \leqq N) 中,整数 A_i, B_i, C_i, D_i (0 \leqq A_i \leqq C_i \leqq W,0 \leqq B_i \leqq D_i \leqq H) 以空格分隔书写。这表示第 i 条切割线是连接 (A_i, B_i) 和 (C_i, D_i) 的线段。这条线段是与纸张某条边平行的线段。也就是说,在A_i = C_i 和 B_i = D_i 中正好有 1 条成立。此外,某条切割线与平行它的其他切割线不会有交点,某条切割线与平行的纸边也不会有交点。在标准输出中,输出表示纸张被分成多少部分的整数
出力
所有输入数据满足以下条件 1 行上。
制限
满足以下条件
- 1 \leqq W \leqq 1\,000\,000\,000.
- 1 \leqq H \leqq 1\,000\,000\,000.
- 1 \leqq N \leqq 100\,000.
小課題
小課題 1 [5 点]
不同的切割线形成的有交点的组合数量为
- W \leqq 1\,000.
- H \leqq 1\,000.
- N \leqq 1\,000.
小課題 2 [5 点]
不同的切割线形成的有交点的组合数量为
- N \leqq 1\,000.
小課題 3 [20 点]
条切割线的组数为 2 不超过100\,000 。
小課題 4 [20 点]
从切割线上各个点出发,可以沿着若干条切割线到达纸张的某一边上的点。
小課題 5 [50 点]
没有额外的限制。
入力例 1
10 10 5 6 0 6 7 0 6 7 6 2 3 9 3 2 3 2 10 1 9 8 9
出力例 1
4
在这个输入的情况下,切割线如下面的图所示。

因此,纸张通过切割线被分成 4 个部分。顺便提一下,这个输入满足小课题的条件。 4 符合条件。
入力例 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
出力例 2
5
在这个输入的情况下,切割线如下面的图所示。

因此,纸张通过切割线被分成 5 个部分。顺便提一下,这个输入满足小课题的条件。 4 条件。