Landet IOI har besluttet å gjennomføre en omfattende utbygging av transportnettverket sitt. IOI er representert som et $xy$-koordinatplan, der det ligger $N$ byer. Den $i$-te byen ($1 \le i \le N$) er representert som et punkt $(X_i, Y_i)$. Utbyggingen av transportnettverket gjennomføres etter følgende prosedyre:

• Bygg internasjonale flyplasser i noen av de $N$ byene. Minst én internasjonal flyplass må bygges. Hver internasjonale flyplass som bygges medfører en fast kostnad.
• Bygg flere veier som forbinder byer. En vei er et linjesegment parallelt med $x$-aksen eller $y$-aksen som direkte forbinder to punkter som representerer byer. Hver vei som bygges medfører en kostnad lik lengden sin.

Samtidig må følgende betingelser være oppfylt:

• Det er $M$ områder i IOI der veier ikke kan bygges på grunn av dårlige grunnforhold eller andre årsaker. Hvert område er representert som et rektangel; det $j$-te rektangelet ($1 \le j \le M$) har sitt nederste venstre hjørne i $(P_j, Q_j)$ og sitt øverste høyre hjørne i $(R_j, S_j)$ (der $P_j < R_j$ og $Q_j < S_j$). Ingen vei kan ha noe skjæringspunkt med noen av de $M$ områdene. Områdene inkluderer grensene sine, og ingen vei kan ha noe skjæringspunkt med grensen til noe rektangel som representerer et område.
• Det må være mulig å nå en by med en internasjonal flyplass fra enhver av de $N$ byene ved å reise gjentatte ganger langs veier til andre byer.

Det er $C$ byggefirmaer som er kandidater for dette prosjektet. Det $k$-te byggefirmaet ($1 \le k \le C$) har en kostnad på $B_k$ for å bygge én internasjonal flyplass og kan bygge høyst $H_k$ internasjonale flyplasser (kostnaden for å bygge veier avhenger ikke av byggefirmaet, og det er ingen begrensninger på antall eller lengde på veiene). For hvert byggefirma ønsker vi å finne den minste totalkostnaden for å bygge ut transportnettverket slik at betingelsene ovenfor er oppfylt.

Siden antallet internasjonale flyplasser som kan bygges er lite, kan det være byggefirmaer som ikke kan bygge ut transportnettverket samtidig som betingelsene oppfylles. I slike tilfeller skal du rapportere at betingelsene ikke kan oppfylles i stedet for totalkostnaden.

Oppgave

Gitt heltallet $N$ som representerer antall byer i IOI og koordinatene deres, heltallet $M$ som representerer antall områder der veier ikke kan bygges og koordinatene deres, og heltallet $C$ som representerer antall kandiderende byggefirmaer og informasjonen deres, skriv et program som beregner den minste totalkostnaden for hvert byggefirma for å bygge ut transportnettverket samtidig som betingelsene beskrevet i oppgaveteksten er oppfylt.

Inndata

Les følgende inndata fra standard inndata:

• Den første linjen inneholder tre heltall $N, M, C$, adskilt med mellomrom, som representerer henholdsvis antall byer i IOI, antall områder der veier ikke kan bygges, og antall kandiderende byggefirmaer.
• Den $i$-te linjen av de følgende $N$ linjene ($1 \le i \le N$) inneholder to heltall $X_i, Y_i$, adskilt med mellomrom, som representerer koordinatene $(X_i, Y_i)$ til den $i$-te byen.
• Den $j$-te linjen av de følgende $M$ linjene ($1 \le j \le M$) inneholder fire heltall $P_j, Q_j, R_j, S_j$, adskilt med mellomrom, som representerer koordinatene til det nederste venstre punktet $(P_j, Q_j)$ og det øverste høyre punktet $(R_j, S_j)$ til det $j$-te rektangelet der veier ikke kan bygges.
• Den $k$-te linjen av de følgende $C$ linjene ($1 \le k \le C$) inneholder to heltall $B_k, H_k$, adskilt med mellomrom, som representerer at det $k$-te kandiderende byggefirmaet har en kostnad på $B_k$ per internasjonal flyplass og kan bygge høyst $H_k$ internasjonale flyplasser.

Utdata

Skriv ut $C$ linjer til standard utdata. Den $k$-te linjen ($1 \le k \le C$) skal inneholde et enkelt heltall som representerer den minste totalkostnaden for det $k$-te kandiderende byggefirmaet for å gjennomføre dette prosjektet. Men hvis det $k$-te kandiderende byggefirmaet ikke kan gjennomføre prosjektet samtidig som betingelsene oppfylles, skriv ut $-1$ i stedet.

Begrensninger

Alle inndata oppfyller følgende betingelser:

• $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$).
• Ingen to byer ligger på de samme koordinatene.
• $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$).
• Ingen områder inneholder en by i sitt indre eller på grensen sin.
• $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$).

Deloppgaver

Deloppgave 1 [10 poeng]

Oppfyller følgende betingelser:

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

Deloppgave 2 [30 poeng]

Oppfyller følgende betingelse:

• $C \le 100$.

Deloppgave 3 [30 poeng]

Oppfyller følgende betingelse:

• $M \le 100$.

Deloppgave 4 [30 poeng]

Ingen ytterligere begrensninger.

Eksempler

Inndata 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

Merk

Eksempelinndataene kan illustreres som følger. Rektanglene med tykke linjer angir områdene der veier ikke kan bygges.

Selv om det er mulig å bygge veier som forbinder By 2 og By 4, samt By 3 og By 4, er det ikke mulig å bygge en vei mellom By 1 og By 2 fordi den ville krysse et område der veier ikke kan bygges. På samme måte er det ikke mulig å bygge en vei mellom By 1 og By 3 (merk at veier ikke må ha noe skjæringspunkt med grensene til rektanglene).

Det første byggefirmaet kan bygge høyst 4 internasjonale flyplasser til en kostnad på 7 hver. I dette tilfellet er det best å bygge internasjonale flyplasser i alle byene uten å bygge noen veier, og totalkostnaden er $7 \times 4 = 28$.

Det andre byggefirmaet kan bygge høyst 3 internasjonale flyplasser til en kostnad på 10 hver. I dette tilfellet er det best å for eksempel bygge veier med lengde 9 som forbinder By 2 og By 4, samt By 3 og By 4, og bygge internasjonale flyplasser i By 1 og By 2. Totalkostnaden er $10 \times 2 + 9 + 9 = 38$.

Det tredje byggefirmaet kan bygge høyst 1 internasjonal flyplass til en kostnad på 1 hver, men siden By 1 ikke kan få bygget vei til noen annen by, må minst 2 internasjonale flyplasser bygges for å oppfylle betingelsene i oppgaveteksten. Dermed er det klart at dette firmaet ikke kan gjennomføre prosjektet, så vi skriver ut $-1$.