소 T는 전시 구역을 $n \times n$ 크기의 2차원 격자로 계획했습니다. 격자의 가장 바깥쪽은 전시 벽으로 둘러싸여 있습니다. 즉, 가로 좌표나 세로 좌표가 $0$ 또는 $n+1$인 모든 격자는 전시 벽 격자입니다. 또한, 전시 구역 내부에는 $m$개의 전시 벽 격자가 흩어져 있으며, 그중 $i$ ($1 \le i \le m$) 번째 격자의 좌표는 $(x_i, y_i)$입니다. 모든 전시 벽 격자는 서로 4-연결(4-connected)되어 있음이 보장됩니다.

현장 배치 테스트를 거쳐 소 T는 격자 사이를 이동할 때의 소요 시간 규칙을 정리했습니다. 구체적으로, 격자 사이에는 다음과 같은 두 가지 이동 방식이 있습니다.

• 상하좌우 방향으로 한 칸 이동, 즉 $(x, y)$에서 $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$ 중 인접한 격자로 이동하는 데는 2 단위 시간이 소요됩니다.
• 대각선 방향으로 한 칸 이동, 즉 $(x, y)$에서 $(x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1)$ 중 대각선 격자로 이동하는 데는 3 단위 시간이 소요됩니다.

물론, 이동하려는 목표 위치는 전시 벽 격자일 수 없습니다. 주의: 대각선 방향으로 이동할 때는 두 개의 대각선 전시 벽 격자 사이의 틈을 통해 직접 통과할 수 있습니다. 예를 들어, $(x, y+1)$과 $(x+1, y)$가 모두 전시 벽 격자라 하더라도, 3 단위 시간을 소요하여 $(x, y)$에서 $(x+1, y+1)$로 대각선 이동할 수 있습니다.

소 S는 전시 구역에 총 $q$개의 보물을 배치했습니다. $i$ ($1 \le i \le q$) 번째 보물에 대해, 그녀는 보물의 위치 $(tx_i, ty_i)$를 공개하며, 공개 시 당신의 위치는 $(sx_i, sy_i)$입니다. 각 보물을 가장 빠르게 획득하기 위해, 당신이 위치한 곳에서 보물이 있는 곳까지 이동하는 데 걸리는 최단 시간을 계산해야 합니다.

입력

입력의 첫 번째 줄에는 세 개의 정수 $n, m, q$ ($1 \le n \le 10^5, 1 \le m, q \le 3 \times 10^5$)가 주어집니다.

다음 $m$개의 줄에는 $i$ ($1 \le i \le m$) 번째 전시 벽 격자의 좌표 $x_i, y_i$ ($1 \le x_i, y_i \le n$)가 주어집니다. 모든 $(x_i, y_i)$는 서로 다름이 보장됩니다.

다음 $q$개의 줄에는 $i$ ($1 \le i \le q$) 번째 보물에 대해 당신의 위치와 보물의 위치를 나타내는 네 개의 정수 $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$)가 주어집니다. $(sx_i, sy_i)$와 $(tx_i, ty_i)$는 모두 전시 벽 격자가 아님이 보장됩니다.

출력

$q$개의 줄을 출력하며, 각 줄에는 해당 보물까지의 최단 시간을 나타내는 정수를 출력합니다. 만약 보물이 있는 위치로 이동할 수 없는 경우 $-1$을 출력합니다.

예제

입력 1

4 4 5
2 1
2 2
3 2
3 3
1 1 1 2
1 1 3 1
4 1 1 4
4 4 1 1
2 3 3 1

출력 1

2
16
11
10
11

참고

두 번째 보물에 대해, 다음과 같은 경로로 이동할 수 있습니다: $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, 총 소요 시간은 $2 + 3 + 3 + 3 + 2 + 3 = 16$입니다.