Państwo IOI postanowiło kompleksowo rozbudować swoją sieć transportową. Państwo IOI przedstawiamy jako płaszczyznę współrzędnych $xy$, na której znajduje się $N$ miast. Miasto $i$ ($1\le i\le N$) jest reprezentowane przez punkt $(X_i,Y_i)$. Rozbudowa sieci transportowej przebiega następująco:

• W niektórych spośród $N$ miast buduje się międzynarodowe lotniska. Należy zbudować co najmniej jedno międzynarodowe lotnisko. Budowa każdego lotniska wiąże się z ustalonym kosztem.
• Buduje się pewną liczbę dróg łączących miasta. Każda droga jest odcinkiem równoległym do osi $x$ lub osi $y$, bezpośrednio łączącym punkty reprezentujące miasta. Koszt budowy każdej drogi jest równy jej długości.

Muszą przy tym być spełnione następujące warunki:

• W państwie IOI istnieje $M$ obszarów, w których nie można budować dróg, na przykład ze względu na zły stan podłoża. Każdy obszar jest prostokątem. Lewy dolny wierzchołek prostokąta $j$ ($1\le j\le M$) to $(P_j,Q_j)$, a prawy górny to $(R_j,S_j)$; zachodzi zatem $P_j<R_j$ oraz $Q_j<S_j$. Żadna droga nie może mieć punktu wspólnego z żadnym z $M$ obszarów. Obszary obejmują również swoje brzegi, więc niedozwolone są także drogi mające punkt wspólny z brzegiem któregoś prostokąta.
• Z każdego z $N$ miast musi dać się dotrzeć do miasta z międzynarodowym lotniskiem, wielokrotnie przechodząc drogami z jednego miasta do drugiego.

Do realizacji tego przedsięwzięcia rozważa się $C$ firm budowlanych. Firma $k$ ($1\le k\le C$) pobiera koszt $B_k$ za budowę jednego międzynarodowego lotniska i może zbudować co najwyżej $H_k$ takich lotnisk. Koszt budowy dróg nie zależy od firmy, a liczba i długość dróg nie są ograniczone. Dla każdej firmy chcemy wyznaczyć najmniejszy łączny koszt rozbudowy sieci transportowej spełniającej powyższe warunki.

Może się zdarzyć, że firma nie jest w stanie spełnić tych warunków, ponieważ może zbudować zbyt mało lotnisk. W takim przypadku zamiast łącznego kosztu należy zgłosić, że spełnienie warunków jest niemożliwe.

Zadanie

Mając dane liczbę miast $N$ i ich współrzędne, liczbę obszarów zakazanych $M$ i współrzędne opisujące każdy z nich oraz liczbę rozważanych firm $C$ i informacje o każdej firmie, napisz program wyznaczający dla każdej firmy najmniejszy łączny koszt realizacji przedsięwzięcia zgodnie z warunkami opisanymi w treści zadania.

Wejście

Wczytaj ze standardowego wejścia następujące dane:

• Pierwszy wiersz zawiera trzy liczby całkowite $N,M,C$, oddzielone spacjami, oznaczające odpowiednio liczbę miast w państwie IOI, liczbę obszarów, w których nie można budować dróg, oraz liczbę firm rozważanych do realizacji przedsięwzięcia.
• Wiersz $i$ ($1\le i\le N$) spośród kolejnych $N$ wierszy zawiera dwie liczby całkowite $X_i,Y_i$, oddzielone spacją, oznaczające, że miasto $i$ ma współrzędne $(X_i,Y_i)$.
• Wiersz $j$ ($1\le j\le M$) spośród kolejnych $M$ wierszy zawiera cztery liczby całkowite $P_j,Q_j,R_j,S_j$, oddzielone spacjami. Oznaczają one, że lewy dolny wierzchołek prostokąta opisującego obszar zakazany $j$ ma współrzędne $(P_j,Q_j)$, a prawy górny — $(R_j,S_j)$.
• Wiersz $k$ ($1\le k\le C$) spośród kolejnych $C$ wierszy zawiera dwie liczby całkowite $B_k,H_k$, oddzielone spacją. Firma $k$ pobiera koszt $B_k$ za budowę jednego międzynarodowego lotniska i może zbudować co najwyżej $H_k$ takich lotnisk.

Wyjście

Wypisz na standardowe wyjście $C$ wierszy. W wierszu $k$ ($1\le k\le C$) wypisz jedną liczbę całkowitą: najmniejszy łączny koszt realizacji przedsięwzięcia przez firmę $k$. Jeżeli firma $k$ nie jest w stanie zrealizować przedsięwzięcia z zachowaniem wymaganych warunków, wypisz zamiast tego liczbę całkowitą $-1$.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki:

• $1\le N\le200\,000$.
• $1\le M\le200\,000$.
• $1\le C\le500\,000$.
• $0\le X_i\le1\,000\,000\,000$ ($1\le i\le N$).
• $0\le Y_i\le1\,000\,000\,000$ ($1\le i\le N$).
• Żadne dwa miasta nie mają takich samych współrzędnych.
• $0\le P_j<R_j\le1\,000\,000\,000$ ($1\le j\le M$).
• $0\le Q_j<S_j\le1\,000\,000\,000$ ($1\le j\le M$).
• Żaden obszar zakazany nie zawiera miasta ani w swoim wnętrzu, ani na brzegu.
• $1\le B_k\le1\,000\,000\,000$ ($1\le k\le C$).
• $1\le H_k\le N$ ($1\le k\le C$).

Podzadania

Podzadanie 1 [10 punktów]

Spełnione są następujące warunki:

• $M\le100$.
• $C\le100$.

Podzadanie 2 [30 punktów]

Spełniony jest następujący warunek:

• $C\le100$.

Podzadanie 3 [30 punktów]

Spełniony jest następujący warunek:

• $M\le100$.

Podzadanie 4 [30 punktów]

Brak dodatkowych ograniczeń.

Przykład

Wejście 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

Wyjście 1

28
38
-1

Poniższy rysunek przedstawia ten przykład. Prostokąty narysowane grubymi liniami oznaczają obszary, w których nie można budować dróg.

Można zbudować drogi łączące miasta $2$ i $4$ oraz miasta $3$ i $4$. Nie można jednak zbudować drogi między miastami $1$ i $2$, ponieważ przecinałaby obszar zakazany. Z tego samego powodu nie można zbudować drogi między miastami $1$ i $3$. Pamiętaj, że droga nie może mieć punktu wspólnego nawet z brzegiem prostokąta.

Pierwsza firma może zbudować co najwyżej $4$ międzynarodowe lotniska, każde za $7$. Najlepiej nie budować żadnych dróg i zbudować lotnisko w każdym mieście. Łączny koszt wynosi wtedy $7\times4=28$.

Druga firma może zbudować co najwyżej $3$ międzynarodowe lotniska, każde za $10$. Optymalnym rozwiązaniem jest na przykład zbudowanie dwóch dróg długości $9$, łączących miasta $2$ i $4$ oraz miasta $3$ i $4$, a także lotnisk w miastach $1$ i $2$. Łączny koszt wynosi wtedy $10\times2+9+9=38$.

Trzecia firma może zbudować co najwyżej jedno międzynarodowe lotnisko za $1$. Ponieważ miasta $1$ nie da się połączyć drogą z żadnym innym miastem, do spełnienia warunków zadania potrzebne są co najmniej dwa lotniska. Ta firma nie jest więc w stanie zrealizować przedsięwzięcia i należy wypisać $-1$.