BEARs

무한한 도시가 남북 방향과 동서 방향으로 난 무한히 많은 양방향 도로로 인해 단위 정사각형 블록으로 나뉘어 있다. 남북 방향 도로 중 하나의 번호는 $0$이며, 동쪽으로 갈수록 번호가 커지고 서쪽으로 갈수록 작아진다. 마찬가지로 동서 방향 도로 중 하나의 번호는 $0$이며, 북쪽으로 갈수록 커지고 남쪽으로 갈수록 작아진다.

각 교차점은 그곳에서 만나는 두 도로 번호의 순서쌍 $(A, B)$로 나타낸다(첫 번째 숫자는 남북 방향 도로의 번호이다). 일부 단위 도로 구간은 특별한 구간으로, 간선 도로(main street)라고 부른다.

순찰 중이던 보안관 Wolf는 교차점 $(A, B)$에서 악명 높은 BEAR 일당의 차량을 발견한다. 일당은 교차점 $(0, 0)$ 옆의 꿀 창고를 터려고 하며, Wolf는 그들을 창고에서 최대한 멀리 떨어뜨려 한다.

일당은 아직 범죄를 저지르지 않았으므로 Wolf는 체포할 수 없고, 길을 막을 수만 있다. BEAR 일당이 어떤 교차점에 들어오기 직전에, Wolf는 먼저 그곳에 도착해 그 교차점에서 만나는 (최대 네 개의) 단위 구간 중 정확히 하나를 막을 수 있다. 다만 간선 도로에 속하는 구간은 절대 막을 수 없다. 일당은 그 교차점으로 들어갈 수는 있지만, 막힌 구간을 통해 빠져나올 수는 없다. Wolf는 일당이 들어가는 교차점마다 서로 다른 구간을 막을 수 있다. 시작 교차점 $(A, B)$에서는 일당이 이미 멈춰 있으므로 아무것도 막혀 있지 않다.

창고로부터의 거리는 $\max(|x|, |y|)$로 정의한다. 일당이 어떻게 움직이든, Wolf가 어떻게 막든, 일당이 도달할 수 있는 모든 교차점 $(x, y)$가 $\max(|x|, |y|) \ge D$를 만족하도록 하는 가장 큰 값 $D$를 구하라. 즉, $D$는 Wolf가 일당을 창고로부터 강제로 떨어뜨려 놓을 수 있는 최소 거리이다.

첫 째 줄에는 두 정수 $A$와 $B$ ($|A| \le 10^6$, $|B| \le 10^6$)가 주어진다. 이는 BEAR 일당의 시작 교차점이다.

둘째 줄에는 간선 도로의 개수를 나타내는 정수 $N$ ($0 \le N \le 500$)이 주어진다.

이어지는 $N$개의 줄에는 각각 네 정수 $X_1, Y_1, X_2, Y_2$ ($|X_i| \le 10^6$, $|Y_i| \le 10^6$)가 주어진다. 교차점 $(X_1, Y_1)$과 $(X_2, Y_2)$ 사이의 모든 단위 구간은 간선 도로이다. 항상 $X_1 = X_2$ 또는 $Y_1 = Y_2$가 성립한다.

$D$의 최댓값을 정수 하나로 출력한다.

첫 번째 예제에서 BEAR 일당은 창고로부터 거리 $1$인 교차점까지는 다달할 수 있지만, 보안관 Wolf는 그보다 더 가까이 접근하지 못하도록 막을 수 있으므로 답은 $1$이다. 일당이 아무리 오래 시도해도 Wolf는 그들을 항상 거리 $1$ 이상으로 유지할 수 있다. 아래 그림은 그러한 접근 방법 하나를 보여준다.