Tiểu T quy hoạch khu vực triển lãm thành một lưới hai chiều kích thước $n \times n$. Vành ngoài cùng của lưới được bao quanh bởi một vòng tường triển lãm, nghĩa là tất cả các ô có tọa độ $x$ hoặc $y$ bằng $0$ hoặc $n+1$ đều là các ô tường triển lãm. Ngoài ra, bên trong khu vực triển lãm còn có $m$ ô tường triển lãm rải rác, trong đó ô thứ $i$ ($1 \le i \le m$) có tọa độ là $(x_i, y_i)$. Đảm bảo rằng tất cả các ô tường triển lãm tạo thành một cấu trúc liên thông 4 chiều.

Sau khi thử nghiệm thực tế, Tiểu T đã tổng kết được quy luật tiêu tốn thời gian khi di chuyển giữa các ô trong lưới. Cụ thể, có hai cách di chuyển giữa các ô như sau:

• Di chuyển một ô theo hướng lên, xuống, trái, phải, tức là từ $(x, y)$ di chuyển đến một trong các ô lân cận $(x-1, y), (x+1, y), (x, y-1), (x, y+1)$, tiêu tốn $2$ đơn vị thời gian.
• Di chuyển một ô theo hướng chéo, tức là từ $(x, y)$ di chuyển đến một trong các ô chéo $(x-1, y-1), (x-1, y+1), (x+1, y-1), (x+1, y+1)$, tiêu tốn $3$ đơn vị thời gian.

Tất nhiên, vị trí đích của việc di chuyển không được là ô tường triển lãm. Lưu ý: Khi di chuyển theo hướng chéo, bạn có thể đi xuyên qua khe hở giữa hai ô tường triển lãm nằm chéo nhau. Ví dụ, ngay cả khi cả $(x, y+1)$ và $(x+1, y)$ đều là các ô tường triển lãm, bạn vẫn có thể tiêu tốn $3$ đơn vị thời gian để di chuyển trực tiếp từ $(x, y)$ theo đường chéo đến $(x+1, y+1)$.

Tiểu S đã bố trí tổng cộng $q$ kho báu trong khu vực triển lãm. Đối với kho báu thứ $i$ ($1 \le i \le q$), cô ấy sẽ công bố vị trí của nó là $(tx_i, ty_i)$, và vị trí của bạn tại thời điểm công bố là $(sx_i, sy_i)$. Để giành được từng kho báu với tốc độ nhanh nhất, bạn cần tính toán thời gian ngắn nhất để di chuyển từ vị trí hiện tại của bạn đến vị trí của kho báu.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên dương $n, m, q$ ($1 \le n \le 10^5, 1 \le m, q \le 3 \times 10^5$).

$m$ dòng tiếp theo, dòng thứ $i$ ($1 \le i \le m$) chứa hai số nguyên dương $x_i, y_i$ ($1 \le x_i, y_i \le n$), biểu thị tọa độ của ô tường triển lãm thứ $i$. Đảm bảo tất cả các $(x_i, y_i)$ là phân biệt.

$q$ dòng tiếp theo, dòng thứ $i$ ($1 \le i \le q$) chứa bốn số nguyên dương $sx_i, sy_i, tx_i, ty_i$ ($1 \le sx_i, sy_i, tx_i, ty_i \le n$), biểu thị vị trí của bạn và vị trí của kho báu khi công bố kho báu thứ $i$. Đảm bảo rằng $(sx_i, sy_i)$ và $(tx_i, ty_i)$ đều không phải là ô tường triển lãm.

Dữ liệu ra

In ra $q$ dòng, mỗi dòng một số nguyên biểu thị kết quả. Đặc biệt, nếu bạn không thể di chuyển đến vị trí của kho báu, hãy in ra $-1$.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

2
16
11
10
11

Ghi chú

Đối với kho báu thứ hai, bạn có thể di chuyển theo lộ trình sau: $(1, 1) \to (1, 2) \to (2, 3) \to (3, 4) \to (4, 3) \to (4, 2) \to (3, 1)$, tổng thời gian tiêu tốn là $2 + 3 + 3 + 3 + 2 + 3 = 16$.