题目描述

Porto and the nearby Douro Valley are famous for producing port wine. Wine lovers from all over the world come here to enjoy this sweet wine where it is made. The International Consortium of Port Connoisseurs (ICPC) is organizing tours to the vineyards that are upstream on the Douro River. To make visits more pleasurable for tourists, the ICPC has recently installed sun tarps above the vineyards. The tarps protect tourists from sunburn when strolling among the vines and sipping on a vintage port.

Unfortunately, there is a small problem with the tarps. Grapes need sunlight and water to grow. While the tarps let through enough sunlight, they are entirely waterproof. This means that rainwater might not reach the vineyards below. If nothing is done, this year's wine harvest is in peril!

The ICPC wants to solve their problem by puncturing the tarps so that they let rainwater through to the vineyards below. Since there is little time to waste before the rainy season starts, the ICPC wants to make the minimum number of punctures that achieve this goal. We will consider a two-dimensional version of this problem. The vineyard to be watered is an interval on the $x$-axis, and the tarps are modeled as line segments above the $x$-axis. The tarps are slanted, that is, not parallel to the $x-$ or $y-$ axes (see Figure F.1 for an example). Rain falls straight down from infinitely high. When any rain falls on a tarp, it flows toward the tarp's lower end and falls off from there, unless there is a puncture between the place where the rain falls and the tarp's lower end—in which case the rain will fall through the puncture instead. After the rain falls off a tarp, it continues to fall vertically.

This repeats until the rain hits the ground (the $x$-axis).

For legal reasons you have to ensure that at least some of the rain that reaches the vineyard originated from directly above the vineyard. This is to prevent any vineyard from stealing all their rain from neighboring vineyards (see the second sample input for an example).

输入格式

The first line of input contains three integers $l$ , $r$ and $n$, where $(l,r)$ $(0 \leq l \lt r \leq 10^9)$ is the interval representing the vineyard and $n$ $(0 \leq n \leq 5 \times 10^5)$ is the number of tarps. Each of the following $n$ linesdescribes a tarp and contains four integers $x_1, y_1, x_2, y_2$ , where $(x_1, y_1)$ is the position of the tarp's lowerend and $(x_2, y_2)$ is the position of the higher end $(0 \leq x_1, x_2 \leq 10^9 , x_1≠x_2,$ and $0 \lt y_1 \lt y_2 \leq 10^9)$. The $x$-coordinates given in the input ($l$, $r$, and the values of $x_1$ and $x_2$ for all tarps) are all distinct. Thetarps described in the input will not intersect, and no endpoint of a tarp will lie on another tarp.

输出格式

Output the smallest number of punctures that need to be made to get some rain falling from above the vineyard to the vineyard.

题目大意

波尔图和附近的杜罗河谷以生产波尔图葡萄酒而闻名。来自世界各地的葡萄酒爱好者来到这里，在这里品尝酿制的甜酒。国际港口鉴赏家协会（ICPC）正在组织参观杜罗河上游的葡萄园。为了让游客更愉快地参观，ICPC最近在葡萄园上方安装了防晒布。当游客漫步在藤蔓间，在一个古老的港口啜饮时，防水布可以保护他们免受晒伤。

不幸的是，防水布有一个小问题。葡萄生长需要阳光和水。虽然防水油布能让足够的阳光透过，但它们是完全防水的。这意味着雨水可能无法到达下面的葡萄园。如果不采取任何行动，今年的葡萄酒收成将岌岌可危！

ICPC希望通过刺穿防水布来解决他们的问题，这样他们可以让雨水通过下面的葡萄园。由于雨季开始前几乎没有时间可以浪费，ICPC希望实现这一目标的穿刺次数最少。我们将考虑这个问题的二维版本。要浇水的葡萄园是xx轴上的一个间隔，防水布被建模为xx轴上方的线段。防水布是倾斜的，也就是说，与x-x不平行−还是y-y−轴（示例见图F.1）。雨从无限高的地方直下。当任何雨水落在防水油布上时，雨水会流向防水油布的下端并从那里落下，除非雨水落下的地方和防水油布的下端之间有一个小孔，在这种情况下，雨水会通过小孔落下。雨水从防水布上落下后，继续垂直下落。

这将重复进行，直到雨水落在地面上（xx轴）。

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

提示

Source: ICPC World Finals 2019 Problem F: Directing Rainfall.