Landet IOI har beslutat att genomföra en omfattande utbyggnad av sitt transportnät. IOI representeras som ett $xy$-koordinatplan, på vilket det finns $N$ städer. Den $i$-te staden ($1 \le i \le N$) representeras som en punkt $(X_i, Y_i)$. Utbyggnaden av transportnätet genomförs enligt följande procedur:

• Bygg internationella flygplatser i några av de $N$ städerna. Minst en internationell flygplats måste byggas. Varje byggd internationell flygplats medför en fast kostnad.
• Bygg flera vägar som förbinder städer. En väg är ett linjesegment parallellt med $x$-axeln eller $y$-axeln som direkt förbinder två punkter som representerar städer. Varje byggd väg medför en kostnad som är lika med dess längd.

Samtidigt måste följande villkor vara uppfyllda:

• Det finns $M$ områden i IOI där vägar inte kan byggas på grund av dåliga markförhållanden eller andra skäl. Varje område representeras som en rektangel; den $j$-te rektangeln ($1 \le j \le M$) har sitt nedre vänstra hörn i $(P_j, Q_j)$ och sitt övre högra hörn i $(R_j, S_j)$ (där $P_j < R_j$ och $Q_j < S_j$). Ingen väg får ha någon skärning med något av de $M$ områdena. Områdena inkluderar sina ränder, och ingen väg får ha någon skärning med randen av någon rektangel som representerar ett område.
• Det måste vara möjligt att nå en stad med en internationell flygplats från vilken som helst av de $N$ städerna genom att upprepade gånger färdas längs vägar till andra städer.

Det finns $C$ byggföretag som är kandidater för detta projekt. Det $k$-te byggföretaget ($1 \le k \le C$) har en kostnad på $B_k$ för att bygga en internationell flygplats och kan bygga högst $H_k$ internationella flygplatser (kostnaden för att bygga vägar beror inte på byggföretaget, och det finns inga begränsningar för antalet eller längden på vägarna). För varje byggföretag vill vi hitta den minsta totalkostnaden för att bygga ut transportnätet så att ovanstående villkor är uppfyllda.

Eftersom antalet internationella flygplatser som kan byggas är litet kan det finnas byggföretag som inte kan bygga ut transportnätet så att villkoren uppfylls. I sådana fall ska du rapportera att villkoren inte kan uppfyllas istället för totalkostnaden.

Uppgift

Givet heltalet $N$ som representerar antalet städer i IOI och deras koordinater, heltalet $M$ som representerar antalet områden där vägar inte kan byggas och deras koordinater, samt heltalet $C$ som representerar antalet kandiderande byggföretag och deras information, skriv ett program som beräknar den minsta totalkostnaden för varje byggföretag att bygga ut transportnätet så att villkoren som beskrivs i problemtexten uppfylls.

Indata

Läs följande indata från standard inmatning:

• Den första raden innehåller tre heltal $N, M, C$, åtskilda av mellanslag, vilka representerar antalet städer i IOI, antalet områden där vägar inte kan byggas respektive antalet kandiderande byggföretag.
• Den $i$-te raden av de följande $N$ raderna ($1 \le i \le N$) innehåller två heltal $X_i, Y_i$, åtskilda av mellanslag, vilka representerar koordinaterna $(X_i, Y_i)$ för den $i$-te staden.
• Den $j$-te raden av de följande $M$ raderna ($1 \le j \le M$) innehåller fyra heltal $P_j, Q_j, R_j, S_j$, åtskilda av mellanslag, vilka representerar koordinaterna för den nedre vänstra punkten $(P_j, Q_j)$ och den övre högra punkten $(R_j, S_j)$ i den $j$-te rektangeln där vägar inte kan byggas.
• Den $k$-te raden av de följande $C$ raderna ($1 \le k \le C$) innehåller två heltal $B_k, H_k$, åtskilda av mellanslag, vilka representerar att det $k$-te kandiderande byggföretaget har en kostnad på $B_k$ per internationell flygplats och kan bygga högst $H_k$ internationella flygplatser.

Utdata

Skriv ut $C$ rader till standard utmatning. Den $k$-te raden ($1 \le k \le C$) ska innehålla ett enda heltal som representerar den minsta totalkostnaden för det $k$-te kandiderande byggföretaget att genomföra detta projekt. Men om det $k$-te kandiderande byggföretaget inte kan genomföra projektet så att villkoren uppfylls, skriv ut $-1$ istället.

Begränsningar

All indata uppfyller följande villkor:

• $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$).
• Inga två städer har samma koordinater.
• $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$).
• Inget område innehåller en stad i sitt inre eller på sin rand.
• $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$).

Deluppgifter

Deluppgift 1 [10 poäng]

Uppfyller följande villkor:

• $M \le 100$.
• $C \le 100$.

Deluppgift 2 [30 poäng]

Uppfyller följande villkor:

• $C \le 100$.

Deluppgift 3 [30 poäng]

Uppfyller följande villkor:

• $M \le 100$.

Deluppgift 4 [30 poäng]

Inga ytterligare begränsningar.

Exempel

Indata 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

Utdata 1

28
38
-1

Förklaring

Exempelindatan kan illustreras som följer. Rektanglarna med tjocka linjer anger de områden där vägar inte kan byggas.

Även om det är möjligt att bygga vägar som förbinder Stad 2 och Stad 4, samt Stad 3 och Stad 4, är det inte möjligt att bygga en väg mellan Stad 1 och Stad 2 eftersom den skulle skära ett område där vägar inte kan byggas. På samma sätt är det inte möjligt att bygga en väg mellan Stad 1 och Stad 3 (observera att vägar inte får ha någon skärning med rektanglarnas ränder).

Det första byggföretaget kan bygga högst 4 internationella flygplatser till en kostnad av 7 vardera. I detta fall är det bäst att bygga internationella flygplatser i alla städer utan att bygga några vägar, och totalkostnaden är $7 \times 4 = 28$.

Det andra byggföretaget kan bygga högst 3 internationella flygplatser till en kostnad av 10 vardera. I detta fall är det bäst att till exempel bygga vägar med längden 9 som förbinder Stad 2 och Stad 4, samt Stad 3 och Stad 4, och bygga internationella flygplatser i Stad 1 och Stad 2. Totalkostnaden är $10 \times 2 + 9 + 9 = 38$.

Det tredje byggföretaget kan bygga högst 1 internationell flygplats till en kostnad av 1 vardera, men eftersom Stad 1 inte kan få någon väg byggd till någon annan stad måste minst 2 internationella flygplatser byggas för att uppfylla villkoren i problemtexten. Det är alltså tydligt att detta företag inte kan genomföra projektet, så vi skriver ut $-1$.