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$ 家候選公司承包時，所需總成本的最小值。如果該公司無法滿足條件，則改印整數 -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$ 之間也無法鋪設道路。注意，道路也不得與長方形邊界有交集。

第一家公司最多能以每座成本 $7$ 興建 $4$ 座國際機場。此時，最佳方式是不鋪設任何道路，而在每個城鎮興建國際機場，總成本為 $7\times 4=28$。

第二家公司最多能以每座成本 $10$ 興建 $3$ 座國際機場。此時，例如鋪設城鎮 $2$ 與 $4$、城鎮 $3$ 與 $4$ 之間各長 $9$ 的道路，並在城鎮 $1$ 和 $2$ 興建國際機場，就是最佳方式。總成本為 $10\times 2+9+9=38$。

第三家公司最多能以每座成本 $1$ 興建 $1$ 座國際機場，但城鎮 $1$ 無法與任何其他城鎮鋪設道路，因此要滿足題目條件，至少需要興建 $2$ 座國際機場。這家公司無法完成工程，所以印出 -1。