Il paese di IOI ha deciso di realizzare uno sviluppo completo della propria rete di trasporti. IOI è rappresentato come un piano cartesiano $xy$, sul quale si trovano $N$ città. La $i$-esima città ($1 \le i \le N$) è rappresentata come un punto $(X_i, Y_i)$. Lo sviluppo della rete di trasporti viene effettuato secondo la seguente procedura:

• Costruire aeroporti internazionali in alcune delle $N$ città. Deve essere costruito almeno un aeroporto internazionale. Ogni aeroporto internazionale costruito comporta un costo fisso.
• Costruire diverse strade che collegano le città. Una strada è un segmento parallelo all'asse $x$ o all'asse $y$ che collega direttamente due punti che rappresentano città. Ogni strada costruita comporta un costo pari alla sua lunghezza.

Allo stesso tempo, devono essere soddisfatte le seguenti condizioni:

• Ci sono $M$ regioni in IOI in cui non è possibile costruire strade a causa delle cattive condizioni del terreno o per altri motivi. Ogni regione è rappresentata come un rettangolo; il $j$-esimo rettangolo ($1 \le j \le M$) ha il suo angolo inferiore sinistro in $(P_j, Q_j)$ e il suo angolo superiore destro in $(R_j, S_j)$ (dove $P_j < R_j$ e $Q_j < S_j$). Nessuna strada può avere alcuna intersezione con nessuna delle $M$ regioni. Le regioni includono i loro confini e nessuna strada può avere alcuna intersezione con il confine di alcun rettangolo che rappresenta una regione.
• Deve essere possibile raggiungere una città dotata di un aeroporto internazionale da ciascuna delle $N$ città viaggiando ripetutamente lungo le strade verso altre città.

Ci sono $C$ imprese di costruzione candidate per questo progetto. La $k$-esima impresa di costruzione ($1 \le k \le C$) sostiene un costo pari a $B_k$ per costruire un aeroporto internazionale e può costruire al massimo $H_k$ aeroporti internazionali (il costo di costruzione delle strade non dipende dall'impresa di costruzione e non ci sono restrizioni sul numero o sulla lunghezza delle strade). Per ciascuna impresa di costruzione, vogliamo trovare il costo totale minimo per sviluppare la rete di trasporti in modo che le condizioni sopra indicate siano soddisfatte.

Poiché il numero di aeroporti internazionali che possono essere costruiti è piccolo, potrebbero esserci imprese di costruzione che non possono sviluppare la rete di trasporti soddisfacendo le condizioni. In tali casi, si richiede di segnalare che le condizioni non possono essere soddisfatte invece del costo totale.

Compito

Dato l'intero $N$ che rappresenta il numero di città in IOI e le loro coordinate, l'intero $M$ che rappresenta il numero di regioni in cui non è possibile costruire strade e le loro coordinate, e l'intero $C$ che rappresenta il numero di imprese di costruzione candidate e le loro informazioni, scrivi un programma che calcoli il costo totale minimo per ciascuna impresa di costruzione per sviluppare la rete di trasporti soddisfacendo le condizioni descritte nel testo del problema.

Dati di ingresso

Leggi i seguenti dati dallo standard input:

• La prima riga contiene tre interi $N, M, C$, separati da spazi, che rappresentano rispettivamente il numero di città in IOI, il numero di regioni in cui non è possibile costruire strade e il numero di imprese di costruzione candidate.
• La $i$-esima delle seguenti $N$ righe ($1 \le i \le N$) contiene due interi $X_i, Y_i$, separati da spazi, che rappresentano le coordinate $(X_i, Y_i)$ della $i$-esima città.
• La $j$-esima delle seguenti $M$ righe ($1 \le j \le M$) contiene quattro interi $P_j, Q_j, R_j, S_j$, separati da spazi, che rappresentano le coordinate del punto inferiore sinistro $(P_j, Q_j)$ e del punto superiore destro $(R_j, S_j)$ del $j$-esimo rettangolo in cui non è possibile costruire strade.
• La $k$-esima delle seguenti $C$ righe ($1 \le k \le C$) contiene due interi $B_k, H_k$, separati da spazi, che indicano che la $k$-esima impresa di costruzione candidata sostiene un costo di $B_k$ per aeroporto internazionale e può costruire al massimo $H_k$ aeroporti internazionali.

Dati di uscita

Scrivi $C$ righe sullo standard output. La $k$-esima riga ($1 \le k \le C$) deve contenere un singolo intero che rappresenta il costo totale minimo affinché la $k$-esima impresa di costruzione candidata realizzi questo progetto. Tuttavia, se la $k$-esima impresa di costruzione candidata non può realizzare il progetto soddisfacendo le condizioni, stampa invece $-1$.

Assunzioni

Tutti i dati di ingresso soddisfano le seguenti condizioni:

• $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$).
• Non ci sono due città con le stesse coordinate.
• $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$).
• Nessuna regione contiene una città al suo interno o sul suo confine.
• $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$).

Subtask

Subtask 1 [10 punti]

Soddisfa le seguenti condizioni:

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

Subtask 2 [30 punti]

Soddisfa la seguente condizione:

• $C \le 100$.

Subtask 3 [30 punti]

Soddisfa la seguente condizione:

• $M \le 100$.

Subtask 4 [30 punti]

Nessun vincolo aggiuntivo.

Esempi

Input 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

Output 1

28
38
-1

Nota

L'input di esempio può essere illustrato come segue. I rettangoli con linee spesse indicano le regioni in cui non è possibile costruire strade.

Sebbene sia possibile costruire strade che collegano la Città 2 e la Città 4, e la Città 3 e la Città 4, non è possibile costruire una strada tra la Città 1 e la Città 2 perché intersecherebbe una regione in cui non è possibile costruire strade. Analogamente, non è possibile costruire una strada tra la Città 1 e la Città 3 (si noti che le strade non devono avere alcuna intersezione con i confini dei rettangoli).

La prima impresa di costruzione può costruire al massimo 4 aeroporti internazionali a un costo di 7 ciascuno. In questo caso, la scelta migliore è costruire aeroporti internazionali in tutte le città senza costruire alcuna strada, e il costo totale è $7 \times 4 = 28$.

La seconda impresa di costruzione può costruire al massimo 3 aeroporti internazionali a un costo di 10 ciascuno. In questo caso, la scelta migliore è costruire, ad esempio, strade di lunghezza 9 che collegano la Città 2 e la Città 4, e la Città 3 e la Città 4, e costruire aeroporti internazionali nella Città 1 e nella Città 2. Il costo totale è $10 \times 2 + 9 + 9 = 38$.

La terza impresa di costruzione può costruire al massimo 1 aeroporto internazionale a un costo di 1 ciascuno, ma poiché dalla Città 1 non è possibile costruire strade verso nessun'altra città, devono essere costruiti almeno 2 aeroporti internazionali per soddisfare le condizioni del problema. Pertanto, è chiaro che questa impresa non può realizzare il progetto, quindi stampiamo $-1$.