题目描述

波尔图和附近的杜罗河谷以生产波特酒而闻名，来自世界各地的葡萄酒爱好者来到这里享用这款甜酒。国际港口鉴赏家协会（the International Consortium of Port Connoisseurs, ICPC）正在组织杜罗河上游的葡萄园之旅。为了让游客更加愉快， ICPC 最近在葡萄园上方安装了防水布。当在葡萄藤中漫步时，防水布可以保护游客免受晒伤。

不幸的是，防水布存在一个小问题。葡萄需要阳光和水才能生长。虽然防水布并不会影响葡萄接受足够的阳光，但会影响葡萄获得足够的水。如果不采取任何措施，今年的葡萄收成将面临危险！

ICPC 希望通过刺破防水布来解决他们的问题，以便雨水流入下面的葡萄园。由于临近雨季，时间紧张， ICPC 希望在让雨水流入葡萄园的前提下，刺穿的洞尽可能少。

我们接下来在二维平面内讨论这个问题。在这个问题中，葡萄园是 $x$ 轴上的一条线段，防水布是位于 $x$ 轴上方的一些线段，这些防水布是倾斜的，即它们不会与 $x$ 轴或 $y$ 轴平行（详见样例 1）。雨从无限高处垂直下落，当雨落到防水布上时，雨将向较低的地方流动，并在最低端下落，但当雨下落的地方和防水布的最低端之间有洞时，雨将会从洞中垂直下落。雨离开防水布后，将会继续垂直下落，直到落到地面（$x$ 轴）为止。

因为一些原因，你需要确保至少有一些落入葡萄园的雨来自这个葡萄园的正上方。这是为了防止其他葡萄园「偷走」别的葡萄园的所有雨水。（详见样例 2）

输入格式

输入的第一行包含三个整数 $l,r,n$，其中 $l,r$ 代表葡萄园所在位置的区间，$n$ 代表安装的防水布的数量。

接下来 $n$ 行，每行输入四个整数 $x_1,y_1,x_2,y_2$ 来描述一个防水布。其中 $(x_1,y_1)$ 代表防水布最低端， $(x_2,y_2)$ 代表防水布最高端。

保证输入中给出的所有 $x$ 坐标（包含 $l,r$，以及所有的 $x_1,x_2$ ）是不同的。所有防水布不会相交，且不存在一个防水布的端点位于另一个防水布上。

输出格式

输出使雨水落入葡萄园需要刺穿的洞的最少数量。

样例 1

10 20 5
32 50 12 60
30 60 8 70
25 70 0 80
15 30 28 40
5 20 14 25

2

样例输入对应下图（其中绿色的线代表葡萄园的位置，黑色的细线代表防水布的位置）：

样例对应的一种最优解如下图（红色点代表刺穿的洞，蓝线代表雨的一条下落轨迹）：

2 4 2
3 2 0 3
5 2 1 5

1

样例输入对应下图：

样例对应的一种最优解如下图（请注意，虽然按照红线可以不用打任何洞，但它违反了至少有一些落入葡萄园的雨来自这个葡萄园的正上方这一原则，绿线的轨迹则是符合要求的）：

数据范围与提示

$ 0 \leq l < r \leq 10^9, 0 \leq n \leq 5\times 10^5, 0 \leq x_1,x_2 \leq 10^9, x_1 \neq x_2 , 0 \leq y_1 < y_2 \leq 10^9 $