IOI 國決定全面建設交通網。IOI 國用 $xy$ 座標平面表示，上面有 $N$ 個城鎮。第 $i$ 個城鎮（$1\le i\le N$）用點 $(X_i,Y_i)$ 表示。交通網會按以下步驟建設。

• 喺 $N$ 個城鎮當中嘅部分城鎮興建國際機場。至少要興建一個國際機場。每興建一個國際機場，都要支付固定成本。
• 興建若干條連接城鎮嘅道路。每條道路係直接連接代表兩個城鎮嘅點、而且平行於 $x$ 軸或者 $y$ 軸嘅線段。每興建一條道路，所需成本等於佢嘅長度。

同時，必須符合以下條件。

• IOI 國有 $M$ 個區域，因為地質情況差等原因，唔可以興建道路。每個區域都係長方形，第 $j$ 個長方形（$1\le j\le M$）嘅左下角係 $(P_j,Q_j)$，右上角係 $(R_j,S_j)$（即係 $P_j<R_j$，而且 $Q_j<S_j$）。任何道路都唔可以同呢 $M$ 個區域中嘅任何一個有共同部分。區域包括邊界，所以道路亦唔可以同代表區域嘅長方形邊界有共同部分。
• 由 $N$ 個城鎮中嘅任何一個出發，都必須可以反覆沿道路前往其他城鎮，最後到達一個有國際機場嘅城鎮。

有 $C$ 間建築公司成為呢個項目嘅候選承辦商。第 $k$ 間建築公司（$1\le k\le C$）興建一個國際機場嘅成本係 $B_k$，最多可以興建 $H_k$ 個國際機場（道路嘅建築成本唔受公司影響，而且道路數量同長度都冇限制）。對於每間建築公司，都希望知道由佢負責建設符合以上條件嘅交通網，所需總成本嘅最小值。

部分公司可能因為可以興建嘅國際機場數量太少，而冇辦法建設符合條件嘅交通網。呢個情況下，請報告無法符合條件，而唔係報告總成本。

任務

畀定表示 IOI 國城鎮數量嘅整數 $N$ 同各城鎮嘅座標、表示唔可以興建道路嘅區域數量嘅整數 $M$ 同各區域嘅座標，以及表示候選建築公司數量嘅整數 $C$ 同各公司嘅資料，請寫一個程式，對每間公司計算建設符合題目條件嘅交通網所需總成本嘅最小值。

輸入格式

由標準輸入讀取以下資料。

• 第一行有三個用空格分隔嘅整數 $N,M,C$，分別表示 IOI 國嘅城鎮數量、唔可以興建道路嘅區域數量，同埋候選承辦建築公司嘅數量。
• 接落嚟 $N$ 行嘅第 $i$ 行（$1\le i\le N$）有兩個用空格分隔嘅整數 $X_i,Y_i$，表示第 $i$ 個城鎮嘅座標係 $(X_i,Y_i)$。
• 接落嚟 $M$ 行嘅第 $j$ 行（$1\le j\le M$）有四個用空格分隔嘅整數 $P_j,Q_j,R_j,S_j$，表示第 $j$ 個唔可以興建道路嘅長方形區域，左下角座標係 $(P_j,Q_j)$，右上角座標係 $(R_j,S_j)$。
• 接落嚟 $C$ 行嘅第 $k$ 行（$1\le k\le C$）有兩個用空格分隔嘅整數 $B_k,H_k$，表示第 $k$ 間候選公司興建一個國際機場需要成本 $B_k$，而且最多可以興建 $H_k$ 個國際機場。

輸出格式

向標準輸出輸出 $C$ 行。第 $k$ 行（$1\le k\le C$）輸出一個整數，表示假如由第 $k$ 間候選公司負責呢個項目，所需總成本嘅最小值。如果第 $k$ 間候選公司冇辦法完成符合條件嘅項目，就改為輸出整數 $-1$。

資料範圍

所有輸入資料都符合以下條件。

• $1\le N\le 200\,000$。
• $1\le M\le 200\,000$。
• $1\le C\le 500\,000$。
• $0\le X_i\le 1\,000\,000\,000$（$1\le i\le N$）。
• $0\le Y_i\le 1\,000\,000\,000$（$1\le i\le N$）。
• 唔會有兩個或者以上城鎮位於同一個座標。
• $0\le P_j<R_j\le 1\,000\,000\,000$（$1\le j\le M$）。
• $0\le Q_j<S_j\le 1\,000\,000\,000$（$1\le j\le M$）。
• 任何區域嘅長方形內部或者邊界都唔會包含城鎮。
• $1\le B_k\le 1\,000\,000\,000$（$1\le k\le C$）。
• $1\le H_k\le N$（$1\le k\le C$）。

子任務

子任務 1 [10 分]

符合以下條件。

• $M\le 100$。
• $C\le 100$。

子任務 2 [30 分]

符合以下條件。

• $C\le 100$。

子任務 3 [30 分]

符合以下條件。

• $M\le 100$。

子任務 4 [30 分]

冇額外限制。

樣例

輸入格式 1

4 2 3
1 1
10 1
1 10
10 10
4 0 8 9
1 4 9 8
7 4
10 3
1 1

輸出格式 1

28
38
-1

說明

呢個輸入例子可以用下圖表示。粗線畫出嘅長方形表示唔可以興建道路嘅區域。

可以興建連接城鎮 $2$ 同城鎮 $4$，以及連接城鎮 $3$ 同城鎮 $4$ 嘅道路，但城鎮 $1$ 同城鎮 $2$ 之間嘅道路會同禁止興建道路嘅區域相交，所以唔可以興建。同樣，城鎮 $1$ 同城鎮 $3$ 之間亦唔可以興建道路（留意道路亦唔可以同長方形嘅邊界有共同部分）。

第一間建築公司最多可以興建 $4$ 個國際機場，每個成本係 $7$。呢個情況下，最好嘅做法係唔興建任何道路，喺所有城鎮都興建國際機場，總成本係 $7\times 4=28$。

第二間建築公司最多可以興建 $3$ 個國際機場，每個成本係 $10$。呢個情況下，一個最佳做法係興建連接城鎮 $2$ 同城鎮 $4$，以及連接城鎮 $3$ 同城鎮 $4$ 嘅道路，兩條都長 $9$，再喺城鎮 $1$ 同城鎮 $2$ 興建國際機場。總成本係 $10\times 2+9+9=38$。

第三間建築公司最多可以興建 $1$ 個國際機場，每個成本係 $1$。但由於城鎮 $1$ 同其他任何城鎮之間都唔可以興建道路，要完成符合題目條件嘅項目，至少需要興建 $2$ 個國際機場。因此呢間公司冇辦法完成項目，所以輸出 $-1$。