Le pays IOI a décidé de développer l'ensemble de son réseau de transport. Il est représenté par le plan de coordonnées $xy$, dans lequel se trouvent $N$ villes. La $i$-ème ville ($1 \le i \le N$) est représentée par le point $(X_i,Y_i)$. Le réseau de transport est aménagé de la manière suivante.

• On construit des aéroports internationaux dans certaines des $N$ villes. Il faut construire au moins un aéroport international. Chaque aéroport international a un coût de construction fixé.
• On construit des routes reliant des villes. Une route est un segment parallèle à l'axe des $x$ ou à l'axe des $y$ qui relie directement les points représentant deux villes. Le coût de construction d'une route est égal à sa longueur.

Les conditions suivantes doivent être satisfaites.

• Dans le pays IOI, il existe $M$ zones où les routes ne peuvent pas être construites, notamment à cause de la mauvaise qualité du terrain. Chaque zone est un rectangle. Le $j$-ème rectangle ($1 \le j \le M$) a pour coin inférieur gauche $(P_j,Q_j)$ et pour coin supérieur droit $(R_j,S_j)$ (donc $P_j<R_j$ et $Q_j<S_j$). Aucune route ne doit avoir de partie commune avec l'une quelconque de ces $M$ zones. Les zones comprennent leur bord : une route ne peut donc pas non plus avoir de point commun avec le bord d'un de ces rectangles.
• Depuis chacune des $N$ villes, il doit être possible d'atteindre une ville possédant un aéroport international en empruntant successivement des routes reliant des villes.

Il y a $C$ entreprises de construction candidates à ce projet. La $k$-ème entreprise ($1 \le k \le C$) demande un coût $B_k$ par aéroport international construit et peut en construire au plus $H_k$. Le coût des routes ne dépend pas de l'entreprise, et leur nombre et leur longueur ne sont pas limités. Pour chaque entreprise, on souhaite déterminer le coût total minimal de l'aménagement d'un réseau de transport satisfaisant les conditions précédentes.

Certaines entreprises ne pourront peut-être pas satisfaire les conditions, car elles ne peuvent pas construire assez d'aéroports internationaux. Dans ce cas, on souhaite que vous signaliez cette impossibilité au lieu de donner un coût total.

Tâche

On vous donne l'entier $N$ indiquant le nombre de villes du pays IOI et leurs coordonnées, l'entier $M$ indiquant le nombre de zones où les routes ne peuvent pas être construites et les coordonnées décrivant chacune de ces zones, ainsi que l'entier $C$ indiquant le nombre d'entreprises candidates et les informations sur chacune d'elles. Écrivez un programme qui calcule, pour chaque entreprise, le coût total minimal de l'aménagement d'un réseau de transport satisfaisant les conditions de l'énoncé.

Entrée

Lisez les données suivantes sur l'entrée standard.

• La première ligne contient trois entiers $N,M,C$ séparés par des espaces : respectivement le nombre de villes du pays IOI, le nombre de zones où les routes ne peuvent pas être construites et le nombre d'entreprises candidates au projet.
• La $i$-ème ligne ($1 \le i \le N$) des $N$ lignes suivantes contient deux entiers $X_i,Y_i$ séparés par un espace. Ils indiquent que les coordonnées de la $i$-ème ville sont $(X_i,Y_i)$.
• La $j$-ème ligne ($1 \le j \le M$) des $M$ lignes suivantes contient quatre entiers $P_j,Q_j,R_j,S_j$ séparés par des espaces. Ils indiquent que le rectangle décrivant la $j$-ème zone interdite aux routes a pour coin inférieur gauche $(P_j,Q_j)$ et pour coin supérieur droit $(R_j,S_j)$.
• La $k$-ème ligne ($1 \le k \le C$) des $C$ lignes suivantes contient deux entiers $B_k,H_k$ séparés par un espace. Ils indiquent que la $k$-ème entreprise candidate demande un coût $B_k$ par aéroport international construit et peut en construire au plus $H_k$.

Sortie

Écrivez $C$ lignes sur la sortie standard. La $k$-ème ligne ($1 \le k \le C$) doit contenir un entier représentant le coût total minimal si le projet est confié à la $k$-ème entreprise candidate. Si cette entreprise ne peut pas réaliser le projet en satisfaisant les conditions, écrivez à la place l'entier $-1$.

Contraintes

Toutes les données d'entrée satisfont les conditions suivantes.

• $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$).
• Deux villes ne se trouvent jamais aux mêmes coordonnées.
• $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$).
• Aucun rectangle de zone interdite ne contient de ville dans son intérieur ou sur son bord.
• $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$).

Sous-tâches

Sous-tâche 1 [10 points]

Les conditions suivantes sont satisfaites.

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

Sous-tâche 2 [30 points]

La condition suivante est satisfaite.

• $C \le 100$.

Sous-tâche 3 [30 points]

La condition suivante est satisfaite.

• $M \le 100$.

Sous-tâche 4 [30 points]

Il n'y a pas de contraintes supplémentaires.

Exemples

Entrée 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

Sortie 1

28
38
-1

Remarque

L'entrée est représentée ci-dessous. Les rectangles tracés en traits épais représentent les zones où les routes ne peuvent pas être construites.

Ville 3 en haut à gauche, ville 4 en haut à droite, ville 1 en bas à gauche et ville 2 en bas à droite.

On peut construire des routes entre les villes $2$ et $4$, ainsi qu'entre les villes $3$ et $4$, mais pas entre les villes $1$ et $2$, car une telle route rencontrerait une zone interdite. De même, on ne peut pas construire de route entre les villes $1$ et $3$. Rappelez-vous qu'une route ne peut pas non plus avoir de point commun avec le bord des rectangles.

La première entreprise peut construire au plus 4 aéroports internationaux, au coût de $7$ chacun. Dans ce cas, il est optimal de construire un aéroport international dans chaque ville sans construire de route. Le coût total est alors $7 \times 4=28$.

La deuxième entreprise peut construire au plus 3 aéroports internationaux, au coût de $10$ chacun. Dans ce cas, une solution optimale consiste, par exemple, à construire deux routes de longueur $9$, l'une entre les villes $2$ et $4$ et l'autre entre les villes $3$ et $4$, puis à construire des aéroports internationaux dans les villes $1$ et $2$. Le coût total est alors $10 \times 2+9+9=38$.

La troisième entreprise peut construire au plus un aéroport international, au coût de $1$. Mais comme aucune route ne peut relier la ville $1$ à une autre ville, il faut construire au moins deux aéroports internationaux pour satisfaire les conditions de l'énoncé. Cette entreprise ne peut donc pas réaliser le projet : il faut écrire $-1$.