IOI-maa on päättänyt toteuttaa liikenneverkkonsa kokonaisvaltaisen kehittämisen. IOI esitetään $xy$-koordinaatistona, jossa on $N$ kaupunkia. $i$-s kaupunki ($1 \le i \le N$) esitetään pisteenä $(X_i, Y_i)$. Liikenneverkon kehittäminen toteutetaan seuraavan menettelyn mukaisesti:

• Rakennetaan kansainvälisiä lentoasemia joihinkin $N$ kaupungista. Vähintään yksi kansainvälinen lentoasema on rakennettava. Jokainen rakennettu kansainvälinen lentoasema aiheuttaa kiinteän kustannuksen.
• Rakennetaan useita kaupunkeja yhdistäviä teitä. Tie on $x$-akselin tai $y$-akselin suuntainen jana, joka yhdistää suoraan kaksi kaupunkeja esittävää pistettä. Jokainen rakennettu tie aiheuttaa sen pituutta vastaavan kustannuksen.

Tällöin seuraavien ehtojen on täytyttävä:

• IOI:ssa on $M$ aluetta, joille teitä ei voida rakentaa huonojen maaperäolosuhteiden tai muiden syiden vuoksi. Jokainen alue esitetään suorakulmiona; $j$-nnen suorakulmion ($1 \le j \le M$) vasen alanurkka on pisteessä $(P_j, Q_j)$ ja oikea ylänurkka pisteessä $(R_j, S_j)$ (missä $P_j < R_j$ ja $Q_j < S_j$). Millään tiellä ei saa olla leikkauspistettä minkään $M$ alueen kanssa. Alueisiin kuuluvat myös niiden reunat, eikä millään tiellä saa olla leikkauspistettä minkään aluetta esittävän suorakulmion reunan kanssa.
• Mistä tahansa $N$ kaupungista on oltava mahdollista päästä kaupunkiin, jossa on kansainvälinen lentoasema, kulkemalla toistuvasti teitä pitkin muihin kaupunkeihin.

Tähän projektiin on ehdolla $C$ rakennusyritystä. $k$-nnelle rakennusyritykselle ($1 \le k \le C$) yhden kansainvälisen lentoaseman rakentaminen maksaa $B_k$, ja se voi rakentaa enintään $H_k$ kansainvälistä lentoasemaa (teiden rakentamiskustannukset eivät riipu rakennusyrityksestä, eikä teiden lukumäärälle tai pituudelle ole rajoituksia). Haluamme selvittää kullekin rakennusyritykselle pienimmän kokonaiskustannuksen liikenneverkon kehittämiseksi siten, että yllä olevat ehdot täyttyvät.

Koska rakennettavissa olevien kansainvälisten lentoasemien lukumäärä on pieni, jotkin rakennusyritykset eivät välttämättä pysty kehittämään liikenneverkkoa ehtojen mukaisesti. Tällaisissa tapauksissa ilmoita kokonaiskustannuksen sijaan, ettei ehtoja voida täyttää.

Tehtävä

Kun annetaan IOI:n kaupunkien lukumäärää kuvaava kokonaisluku $N$ ja niiden koordinaatit, niiden alueiden lukumäärää, joille teitä ei voida rakentaa, kuvaava kokonaisluku $M$ ja niiden koordinaatit, sekä ehdolla olevien rakennusyritysten lukumäärää kuvaava kokonaisluku $C$ ja niiden tiedot, kirjoita ohjelma, joka laskee kullekin rakennusyritykselle pienimmän kokonaiskustannuksen liikenneverkon kehittämiseksi tehtävänannossa kuvattujen ehtojen mukaisesti.

Syöte

Lue seuraavat tiedot vakiosyötteestä:

• Ensimmäinen rivi sisältää välilyönnein erotettuina kolme kokonaislukua $N, M, C$, jotka vastaavat IOI:n kaupunkien lukumäärää, niiden alueiden lukumäärää, joille teitä ei voida rakentaa, sekä ehdolla olevien rakennusyritysten lukumäärää.
• Seuraavista $N$ rivistä $i$-s rivi ($1 \le i \le N$) sisältää välilyönnein erotettuina kaksi kokonaislukua $X_i, Y_i$, jotka esittävät $i$-nnen kaupungin koordinaatteja $(X_i, Y_i)$.
• Seuraavista $M$ rivistä $j$-s rivi ($1 \le j \le M$) sisältää välilyönnein erotettuina neljä kokonaislukua $P_j, Q_j, R_j, S_j$, jotka esittävät vasemman alapisteen $(P_j, Q_j)$ ja oikean yläpisteen $(R_j, S_j)$ koordinaatteja $j$-nnelle suorakulmiolle, jolle teitä ei voida rakentaa.
• Seuraavista $C$ rivistä $k$-s rivi ($1 \le k \le C$) sisältää välilyönnein erotettuina kaksi kokonaislukua $B_k, H_k$, jotka ilmaisevat, että $k$-nnelle ehdolla olevalle rakennusyritykselle kansainvälisen lentoaseman rakentaminen maksaa $B_k$ lentoasemaa kohti ja se voi rakentaa enintään $H_k$ kansainvälistä lentoasemaa.

Tuloste

Tulosta vakiotulosteeseen $C$ riviä. $k$-nnen rivin ($1 \le k \le C$) tulee sisältää yksi kokonaisluku, joka ilmaisee pienimmän kokonaiskustannuksen, jolla $k$-s ehdolla oleva rakennusyritys voi toteuttaa tämän projektin. Jos $k$-s ehdolla oleva rakennusyritys ei kuitenkaan pysty toteuttamaan projektia ehtojen mukaisesti, tulosta sen sijaan $-1$.

Rajoitukset

Kaikki syötetiedot täyttävät seuraavat ehdot:

• $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$).
• Mitkään kaksi kaupunkia eivät sijaitse samoissa koordinaateissa.
• $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$).
• Mikään alue ei sisällä kaupunkia sisäpuolellaan tai reunallaan.
• $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$).

Osatehtävät

Osatehtävä 1 [10 pistettä]

Täyttää seuraavat ehdot:

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

Osatehtävä 2 [30 pistettä]

Täyttää seuraavan ehdon:

• $C \le 100$.

Osatehtävä 3 [30 pistettä]

Täyttää seuraavan ehdon:

• $M \le 100$.

Osatehtävä 4 [30 pistettä]

Ei lisärajoituksia.

Esimerkit

Syöte 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

Tuloste 1

28
38
-1

Huomautus

Esimerkkisyötettä voidaan havainnollistaa seuraavasti. Paksuilla viivoilla piirretyt suorakulmiot osoittavat alueet, joille teitä ei voida rakentaa.

Vaikka kaupungit 2 ja 4 sekä kaupungit 3 ja 4 yhdistävät tiet on mahdollista rakentaa, kaupunkien 1 ja 2 välille ei ole mahdollista rakentaa tietä, koska se leikkaisi alueen, jolle teitä ei voida rakentaa. Vastaavasti kaupunkien 1 ja 3 välille ei voida rakentaa tietä (huomaa, että teillä ei saa olla leikkauspisteitä suorakulmioiden reunojen kanssa).

Ensimmäinen rakennusyritys voi rakentaa enintään 4 kansainvälistä lentoasemaa hintaan 7 kappaleelta. Tässä tapauksessa on parasta rakentaa kansainväliset lentoasemat kaikkiin kaupunkeihin rakentamatta lainkaan teitä, jolloin kokonaiskustannus on $7 \times 4 = 28$.

Toinen rakennusyritys voi rakentaa enintään 3 kansainvälistä lentoasemaa hintaan 10 kappaleelta. Tässä tapauksessa on parasta rakentaa esimerkiksi pituudeltaan 9 olevat tiet yhdistämään kaupungit 2 ja 4 sekä kaupungit 3 ja 4, ja rakentaa kansainväliset lentoasemat kaupunkeihin 1 ja 2. Kokonaiskustannus on $10 \times 2 + 9 + 9 = 38$.

Kolmas rakennusyritys voi rakentaa enintään 1 kansainvälisen lentoaseman hintaan 1 kappaleelta, mutta koska kaupungista 1 ei voida rakentaa tietä mihinkään muuhun kaupunkiin, on rakennettava vähintään 2 kansainvälistä lentoasemaa tehtävänannon ehtojen täyttämiseksi. Näin ollen on selvää, ettei tämä yritys pysty toteuttamaan projektia, joten tulostamme $-1$.