빗물 유도하기

포르투와 인근 도루 밸리는 포트 와인 생산으로 유명하다. 전 세계의 와인 애호가들이 와인이 만들어지는 현지에서 이 달콤한 와인을 즐기러 찾아온다. 국제 포트 와인 감정가 협회(ICPC)는 도루강 상류의 포도밭을 둘러보는 투어를 운영하고 있다. 방문이 더 즐거워지도록 ICPC는 최근 포도밭 위에 햇빛 가리개(타프)를 설치했다. 관광객은 타프 덕분에 포도나무 사이를 거닐고 빈티지 포트를 마실 때 햇볕에 타지 않는다.

그런데 타프에는 문제가 있다. 포도는 자라려면 햇빛과 물이 필요하다. 타프는 햇빛은 충분히 통과시키지만 완전히 방수가 된다. 그래서 빗물이 아래 포도밭까지 닿지 않을 수 있다. 아무 조치도 하지 않으면 올해 수확이 위태롭다.

ICPC는 빗물이 아래 포도밭까지 통과하도록 타프에 구멍을 내려고 한다. 우기가 곧 시작되므로, 목표를 이루는 구멍의 수를 가장 적게 만들려고 한다.

이 문제는 2차원으로 모델링한다. 포도밭은 x축 위의 구간이고, 각 타프는 x축 위에 있는 선분이다. 타프는 x축, y축 어느 쪽과도 평행하지 않게 기울어져 있다(그림 F.1 참고). 빗물은 높은 하늘에서 수직으로 떨어진다. 빗물이 타프에 떨어지면 타프의 아래쪽 끝을 향해 흘러가 그곳에서 떨어진다. 다만 빗물이 떨어진 지점과 아래쪽 끝 사이에 구멍이 있으면, 빗물은 흘러가지 않고 그 구멍으로 떨어진다. 타프에서 떨어진 빗물은 계속 수직으로 내려간다. 이 과정은 빗물이 땅(x축)에 닿을 때까지 반복된다.

법적인 이유로, 포도밭에 닿는 빗물의 적어도 일부는 포도밭 바로 위에서 내린 것이어야 한다. 이는 한 포도밭이 이웃 포도밭의 빗물을 모두 가로채는 것을 막기 위함이다(두 번째 예제 입력 참고).

첫 줄에 세 정수 $\ell$, $r$, $n$이 주어진다. $(\ell, r)$은 포도밭을 나타내는 구간이며 $0 \le \ell < r \le 10^9$이다. $n$은 타프의 개수이며 $0 \le n \le 5 \cdot 10^5$이다. 이어지는 $n$개의 줄에는 각각 타프를 나타내는 정수 $x_1$, $y_1$, $x_2$, $y_2$가 주어진다. $(x_1, y_1)$은 타프의 아래쪽 끝 위치이고, $(x_2, y_2)$는 위쪽 끝 위치이다. 여기서 $0 \le x_1, x_2 \le 10^9$, $x_1 \ne x_2$, $0 < y_1 < y_2 \le 10^9$이다.

입력에 주어지는 x좌표($\ell$, $r$, 모든 타프의 $x_1$, $x_2$ 값)는 모두 서로 다르다. 타프들은 서로 교차하지 않으며, 어떤 타프의 끝점도 다른 타프 위에 놓이지 않는다.

포도밭 바로 위에서 내린 빗물 중 일부가 포도밭에 닿도록 하는 데 필요한 구멍의 최소 개수를 출력한다.