Im Land IOI soll das gesamte Verkehrsnetz ausgebaut werden. Das Land IOI wird als $xy$-Koordinatenebene dargestellt, auf der sich $N$ Städte befinden. Die $i$-te Stadt ($1\le i\le N$) wird durch den Punkt $(X_i,Y_i)$ dargestellt. Der Ausbau des Verkehrsnetzes erfolgt in den folgenden Schritten.

• In einigen der $N$ Städte werden internationale Flughäfen gebaut. Mindestens ein internationaler Flughafen muss gebaut werden. Für jeden internationalen Flughafen fallen feste Baukosten an.
• Es werden einige Straßen gebaut, die Städte miteinander verbinden. Eine Straße ist eine zur $x$- oder $y$-Achse parallele Strecke, die die Punkte zweier Städte direkt verbindet. Die Baukosten einer Straße entsprechen ihrer Länge.

Dabei müssen die folgenden Bedingungen erfüllt sein.

• Im Land IOI gibt es $M$ Gebiete, in denen wegen schlechter Bodenbeschaffenheit oder aus anderen Gründen keine Straßen gebaut werden können. Jedes Gebiet wird durch ein Rechteck dargestellt. Die linke untere Ecke des $j$-ten Rechtecks ($1\le j\le M$) ist $(P_j,Q_j)$, die rechte obere Ecke ist $(R_j,S_j)$; es gilt also $P_j<R_j$ und $Q_j<S_j$. Keine Straße darf mit irgendeinem der $M$ Gebiete einen gemeinsamen Teil haben. Die Gebiete schließen ihren Rand ein, sodass auch keine Straße einen gemeinsamen Teil mit dem Rand eines solchen Rechtecks haben darf.
• Von jeder der $N$ Städte aus muss man eine Stadt mit internationalem Flughafen erreichen können, indem man wiederholt Straßen zu anderen Städten folgt.

Als mögliche Auftragnehmer für dieses Projekt stehen $C$ Bauunternehmen zur Auswahl. Das $k$-te Bauunternehmen ($1\le k\le C$) benötigt Kosten von $B_k$ für den Bau eines internationalen Flughafens und kann höchstens $H_k$ internationale Flughäfen bauen. Die Straßenbaukosten hängen nicht vom Bauunternehmen ab, und weder Anzahl noch Länge der Straßen sind beschränkt. Für jedes Bauunternehmen soll die kleinste Summe der Kosten ermittelt werden, mit der es ein Verkehrsnetz gemäß den obigen Bedingungen bauen kann.

Manche Bauunternehmen können möglicherweise kein Verkehrsnetz bauen, das die Bedingungen erfüllt, weil sie zu wenige internationale Flughäfen bauen können. In diesem Fall soll anstelle der Gesamtkosten gemeldet werden, dass die Bedingungen nicht erfüllt werden können.

Aufgabe

Gegeben sind die ganze Zahl $N$ für die Anzahl der Städte im Land IOI und die Stadtkoordinaten, die ganze Zahl $M$ für die Anzahl der Gebiete, in denen keine Straßen gebaut werden können, und die Koordinaten dieser Gebiete sowie die ganze Zahl $C$ für die Anzahl möglicher Bauunternehmen und die Informationen zu jedem Unternehmen. Schreibe ein Programm, das für jedes Bauunternehmen die kleinste Summe der Kosten für den Bau eines Verkehrsnetzes bestimmt, das die in der Aufgabenstellung beschriebenen Bedingungen erfüllt.

Eingabe

Lies die folgenden Daten von der Standardeingabe.

• Die erste Zeile enthält drei durch Leerzeichen getrennte ganze Zahlen $N,M,C$. Sie geben der Reihe nach die Anzahl der Städte im Land IOI, die Anzahl der Gebiete, in denen keine Straßen gebaut werden können, und die Anzahl möglicher Bauunternehmen an.
• Die $i$-te der folgenden $N$ Zeilen ($1\le i\le N$) enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $X_i,Y_i$. Sie geben an, dass die $i$-te Stadt die Koordinaten $(X_i,Y_i)$ hat.
• Die $j$-te der folgenden $M$ Zeilen ($1\le j\le M$) enthält vier durch Leerzeichen getrennte ganze Zahlen $P_j,Q_j,R_j,S_j$. Sie geben an, dass das Rechteck des $j$-ten Gebiets, in dem keine Straßen gebaut werden können, die linke untere Ecke $(P_j,Q_j)$ und die rechte obere Ecke $(R_j,S_j)$ hat.
• Die $k$-te der folgenden $C$ Zeilen ($1\le k\le C$) enthält zwei durch ein Leerzeichen getrennte ganze Zahlen $B_k,H_k$. Sie geben an, dass das $k$-te mögliche Bauunternehmen Kosten von $B_k$ für einen internationalen Flughafen benötigt und höchstens $H_k$ internationale Flughäfen bauen kann.

Ausgabe

Gib $C$ Zeilen auf der Standardausgabe aus. Gib in der $k$-ten Zeile ($1\le k\le C$) eine ganze Zahl aus, die die kleinste Summe der Kosten angibt, wenn das $k$-te mögliche Bauunternehmen das Projekt durchführt. Falls dieses Unternehmen das Projekt nicht so durchführen kann, dass die Bedingungen erfüllt sind, gib stattdessen die ganze Zahl $-1$ aus.

Beschränkungen

Alle Eingabedaten erfüllen die folgenden Bedingungen.

• $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$).
• Keine zwei oder mehr Städte haben dieselben Koordinaten.
• $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$).
• Kein Gebiet enthält eine Stadt im Inneren oder auf dem Rand seines Rechtecks.
• $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$).

Teilaufgaben

Teilaufgabe 1 [10 Punkte]

Es gelten die folgenden Bedingungen.

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

Teilaufgabe 2 [30 Punkte]

Es gelten die folgenden Bedingungen.

• $C\le 100$.

Teilaufgabe 3 [30 Punkte]

Es gelten die folgenden Bedingungen.

• $M\le 100$.

Teilaufgabe 4 [30 Punkte]

Es gibt keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 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

Ausgabe 1

28
38
-1

Hinweis

Diese Eingabe wird in der folgenden Abbildung dargestellt. Die Rechtecke mit dicken Linien kennzeichnen die Gebiete, in denen keine Straßen gebaut werden können.

Straßen zwischen Stadt $2$ und Stadt $4$ sowie zwischen Stadt $3$ und Stadt $4$ können gebaut werden. Zwischen Stadt $1$ und Stadt $2$ kann jedoch keine Straße gebaut werden, da sie ein Gebiet schneiden würde, in dem keine Straßen gebaut werden können. Ebenso kann zwischen Stadt $1$ und Stadt $3$ keine Straße gebaut werden. Beachte, dass Straßen auch mit dem Rand eines Rechtecks keinen gemeinsamen Teil haben dürfen.

Das erste Bauunternehmen kann höchstens $4$ internationale Flughäfen zu Kosten von jeweils $7$ bauen. In diesem Fall ist es am besten, ohne Straßenbau in jeder Stadt einen internationalen Flughafen zu bauen. Die Gesamtkosten betragen dann $7\times 4=28$.

Das zweite Bauunternehmen kann höchstens $3$ internationale Flughäfen zu Kosten von jeweils $10$ bauen. Eine optimale Möglichkeit besteht darin, zwischen Stadt $2$ und Stadt $4$ sowie zwischen Stadt $3$ und Stadt $4$ jeweils eine Straße der Länge $9$ zu bauen und in Stadt $1$ und Stadt $2$ internationale Flughäfen zu bauen. Die Gesamtkosten betragen dann $10\times 2+9+9=38$.

Das dritte Bauunternehmen kann höchstens $1$ internationalen Flughafen zu Kosten von $1$ bauen. Da aber zwischen Stadt $1$ und keiner anderen Stadt eine Straße gebaut werden kann, benötigt man mindestens $2$ internationale Flughäfen, um die Bedingungen der Aufgabe zu erfüllen. Dieses Bauunternehmen kann das Projekt daher nicht durchführen, weshalb $-1$ ausgegeben wird.