題目背景

在確定好主會場的位置後，小 T 和小 S 開始著手佈置慶典會場。他們在通往主會場的必經之路上，設置了一塊寬闊的展覽區，用於展現十年 THUPC 的精彩畫面。

小 T 將展覽區規劃成了一個巨大的網格，最外圍以及內部的部分格子被設為展覽牆。為了方便大家沿動線參觀，他將所有的展覽牆精心設計為了四連通的結構。

為了讓參觀過程更具趣味性，小 S 決定在這裡舉辦一場尋寶活動。

小 T 將展覽區規劃成一個大小為 $n \times n$ 的二維網格。網格的最外圍由一圈展覽牆包圍，即橫座標或縱座標等於 $0$ 或 $n+1$ 的所有格子均為展覽牆格子。此外，展覽區內部還散佈著 $m$ 個展覽牆格子，其中第 $i$ ($1 \le i \le m$) 個的座標為 $(x_i, y_i)$。保證所有的展覽牆格子之間是四連通的。

經過實地佈景測試，小 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$)，表示第 $i$ 個展覽牆格子的座標。保證所有 $(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$)，表示公佈第 $i$ 個寶藏時你所處的位置與寶藏所在的位置。保證 $(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$。