题目描述

波尔图和附近的杜罗河谷以生产波特酒而闻名，来自世界各地的葡萄酒爱好者来到这里享用这款甜酒。国际港口鉴赏家协会（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$ ）是不同的。所有防水布不会相交，且不存在一个防水布的端点位于另一个防水布上。

输出格式

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

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 $