El país IOI ha decidido renovar toda su red de transporte. El país IOI se representa mediante un plano de coordenadas $xy$, en el que hay $N$ ciudades. La ciudad $i$ ($1 \le i \le N$) se representa mediante el punto $(X_i,Y_i)$. La renovación de la red de transporte se realiza mediante los siguientes pasos.

• Construir aeropuertos internacionales en algunas de las $N$ ciudades. Es necesario construir al menos un aeropuerto internacional. Cada aeropuerto internacional tiene un coste fijo de construcción.
• Construir algunas carreteras que conecten ciudades. Cada carretera es un segmento paralelo al eje $x$ o al eje $y$ que conecta directamente los puntos que representan dos ciudades. El coste de construir cada carretera es igual a su longitud.

Deben cumplirse las siguientes condiciones.

• En el país IOI hay $M$ regiones en las que no se pueden construir carreteras, por motivos como el mal estado del terreno. Cada región se representa mediante un rectángulo. El vértice inferior izquierdo del rectángulo $j$ ($1 \le j \le M$) es $(P_j,Q_j)$ y su vértice superior derecho es $(R_j,S_j)$; es decir, $P_j<R_j$ y $Q_j<S_j$. Ninguna carretera puede tener puntos en común con ninguna de las $M$ regiones. Las regiones incluyen su borde, por lo que tampoco puede haber carreteras que tengan puntos en común con el perímetro de un rectángulo.
• Desde cualquiera de las $N$ ciudades debe ser posible llegar a una ciudad que tenga un aeropuerto internacional, recorriendo carreteras para ir de una ciudad a otra repetidamente.

Hay $C$ empresas constructoras candidatas a recibir el encargo. La empresa $k$ ($1 \le k \le C$) cobra un coste de $B_k$ por construir cada aeropuerto internacional y puede construir como máximo $H_k$ aeropuertos internacionales. El coste de construcción de las carreteras no depende de la empresa, y no hay restricciones sobre el número ni la longitud de las carreteras. Para cada empresa, se desea determinar el mínimo coste total de renovar la red de transporte cumpliendo las condiciones anteriores.

Es posible que alguna empresa no pueda renovar la red de transporte cumpliendo las condiciones porque el número de aeropuertos internacionales que puede construir sea demasiado pequeño. En ese caso, se debe indicar que no puede cumplir las condiciones, en lugar de informar de un coste total.

Tarea

Escribe un programa que, dados el entero $N$ y las coordenadas de las ciudades del país IOI, el entero $M$ y las coordenadas que describen cada región en la que no se pueden construir carreteras, y el entero $C$ y la información de cada empresa candidata, determine, para cada empresa, el mínimo coste total de renovar la red de transporte cumpliendo las condiciones del enunciado.

Entrada

Lee los siguientes datos de la entrada estándar.

• La primera línea contiene tres enteros $N,M,C$, separados por espacios, que representan, respectivamente, el número de ciudades del país IOI, el número de regiones en las que no se pueden construir carreteras y el número de empresas candidatas a recibir el encargo.
• La línea $i$ ($1 \le i \le N$) de las siguientes $N$ líneas contiene dos enteros $X_i,Y_i$, separados por un espacio, que indican que las coordenadas de la ciudad $i$ son $(X_i,Y_i)$.
• La línea $j$ ($1 \le j \le M$) de las siguientes $M$ líneas contiene cuatro enteros $P_j,Q_j,R_j,S_j$, separados por espacios. Indican que el vértice inferior izquierdo del rectángulo que representa la región $j$ en la que no se pueden construir carreteras es $(P_j,Q_j)$ y su vértice superior derecho es $(R_j,S_j)$.
• La línea $k$ ($1 \le k \le C$) de las siguientes $C$ líneas contiene dos enteros $B_k,H_k$, separados por un espacio. Indican que la empresa candidata $k$ cobra un coste de $B_k$ por construir cada aeropuerto internacional y puede construir como máximo $H_k$ aeropuertos internacionales.

Salida

Escribe $C$ líneas en la salida estándar. En la línea $k$ ($1 \le k \le C$), escribe un entero que represente el mínimo coste total si la empresa candidata $k$ realiza el proyecto. Si esta empresa no puede realizarlo cumpliendo las condiciones, escribe en su lugar el entero $-1$.

Restricciones

Todos los datos de entrada cumplen las siguientes condiciones.

• $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$).
• No hay dos o más ciudades con las mismas coordenadas.
• $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$).
• Ninguna región contiene una ciudad en el interior ni en el borde de su rectángulo.
• $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$).

Subtareas

Subtarea 1 [10 puntos]

Se cumplen las siguientes condiciones.

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

Subtarea 2 [30 puntos]

Se cumple la siguiente condición.

• $C \le 100$.

Subtarea 3 [30 puntos]

Se cumple la siguiente condición.

• $M \le 100$.

Subtarea 4 [30 puntos]

No hay restricciones adicionales.

Ejemplos

Entrada 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

Salida 1

28
38
-1

La figura siguiente representa este ejemplo. Los rectángulos de líneas gruesas indican las regiones en las que no se pueden construir carreteras.

Las etiquetas 町1, 町2, 町3 y 町4 indican, respectivamente, las ciudades 1, 2, 3 y 4.

Se pueden construir carreteras que conecten la ciudad 2 con la ciudad 4 y la ciudad 3 con la ciudad 4. Sin embargo, no se puede construir una carretera entre la ciudad 1 y la ciudad 2, porque intersectaría una región en la que no se pueden construir carreteras. Del mismo modo, tampoco se puede construir una carretera entre la ciudad 1 y la ciudad 3. Ten en cuenta que una carretera tampoco puede tener puntos en común con el perímetro de un rectángulo.

La primera empresa puede construir como máximo 4 aeropuertos internacionales con un coste de 7 por aeropuerto. En este caso, lo mejor es construir un aeropuerto internacional en cada ciudad sin construir ninguna carretera, con un coste total de $7 \times 4=28$.

La segunda empresa puede construir como máximo 3 aeropuertos internacionales con un coste de 10 por aeropuerto. En este caso, una solución óptima consiste, por ejemplo, en construir una carretera de longitud 9 entre la ciudad 2 y la ciudad 4, otra de longitud 9 entre la ciudad 3 y la ciudad 4, y aeropuertos internacionales en las ciudades 1 y 2. El coste total es $10 \times 2+9+9=38$.

La tercera empresa puede construir como máximo un aeropuerto internacional con un coste de 1. Sin embargo, como no se puede construir ninguna carretera entre la ciudad 1 y ninguna otra ciudad, se necesitan al menos dos aeropuertos internacionales para cumplir las condiciones. Por tanto, esta empresa no puede realizar el proyecto y se escribe $-1$.