산책

낯선 대도시에서 목적지를 찾아가는 일은 쉽지 않습니다. 특히 언제나 가장 짧은 경로만 고집하는 컴퓨터 과학자 커크(Kirk)에게는 더욱 그렇습니다. 미리 계획을 세우면 도움이 됩니다. 도시의 지도가 주어질 때, 커크는 현재 위치에서 목적지까지의 최단 경로를 찾고자 합니다.

도시의 지도는 평면 위의 무한한 격자로 나타낼 수 있으며, 각 칸은 단위 정사각형입니다.

커크는 현재 칸 $(0, 0)$에 있고, 목적지는 칸 $(X, Y)$입니다.

도시에는 $N$개의 건물이 있습니다. 각 건물은 여러 개의 단위 정사각형 칸을 완전히 차지하는 직사각형입니다. 어떤 두 건물도 서로 닿거나 겹치지 않으므로, 커크는 모든 건물의 주위를 자유롭게 걸어 다닐 수 있습니다. 각 건물은 그 건물이 차지하는, 대각선으로 마주 보는 두 칸의 좌표로 주어집니다.

한 번의 이동에서 커크는 상하좌우로 인접한 네 칸 중 하나로 걸어갈 수 있지만, 건물이 차지한 칸으로는 들어갈 수 없습니다. 커크의 현재 위치는 도시의 서쪽 입구이며, 모든 건물이 차지하는 칸의 $x$ 좌표는 항상 $0$보다 큽니다.

건물들의 위치가 주어질 때, 커크의 현재 위치에서 목적지까지 가는 최단 경로의 길이를 구하는 프로그램을 작성하세요. 경로의 길이는 시작 칸을 제외하고 경로에 포함된 칸의 개수입니다.

첫째 줄에 목적지 칸의 좌표를 나타내는 두 정수 $X$, $Y$가 주어집니다 ($1 \le X \le 10^6$, $-10^6 \le Y \le 10^6$).

둘째 줄에 도시의 건물 수를 나타내는 정수 $N$이 주어집니다 ($0 \le N \le 100\,000$).

이어지는 $N$개의 줄에는 각각 네 정수 $X_1$, $Y_1$, $X_2$, $Y_2$가 주어지며, 이는 한 건물이 차지하는 대각선으로 마주 보는 두 칸의 좌표입니다 ($1 \le X_1, X_2 \le 10^6$, $-10^6 \le Y_1, Y_2 \le 10^6$).

최단 경로의 길이 $L$을 정수 하나로 출력하세요. 즉, $(0, 0)$에서 $(X, Y)$까지 가는 최단 경로에서 시작 칸을 제외한 칸의 개수를 출력합니다.

어떤 두 건물도 서로 닿지 않아 이동 가능한 칸들은 모두 연결되어 있으므로, 목적지는 항상 도달할 수 있고 최단 경로의 길이는 유일하게 정해집니다.

아래 그림은 두 예제에서의 최단 경로를 보여줍니다.