O país IOI decidiu renovar toda a sua rede de transportes. O país é representado por um plano de coordenadas $xy$, no qual existem $N$ cidades. A cidade $i$ ($1 \le i \le N$) é representada pelo ponto $(X_i,Y_i)$. A renovação da rede de transportes será realizada da seguinte maneira:

• Construir aeroportos internacionais em algumas das $N$ cidades. É necessário construir pelo menos um aeroporto internacional. Cada aeroporto construído tem um custo fixo.
• Construir algumas estradas ligando cidades. Cada estrada é um segmento de reta paralelo ao eixo $x$ ou ao eixo $y$ que liga diretamente os pontos que representam as cidades. O custo de cada estrada é igual ao seu comprimento.

As seguintes condições devem ser satisfeitas:

• Existem $M$ regiões no país IOI onde não se pode construir estradas, por motivos como condições inadequadas do solo. Cada região é um retângulo. O retângulo $j$ ($1 \le j \le M$) tem canto inferior esquerdo $(P_j,Q_j)$ e canto superior direito $(R_j,S_j)$; portanto, $P_j<R_j$ e $Q_j<S_j$. Nenhuma estrada pode ter qualquer ponto em comum com nenhuma das $M$ regiões. As regiões incluem suas bordas, de modo que também não pode haver estradas com pontos em comum com o contorno dos retângulos.
• Partindo de qualquer uma das $N$ cidades, deve ser possível chegar a uma cidade com aeroporto internacional, percorrendo estradas de uma cidade a outra.

Há $C$ construtoras candidatas a receber o contrato deste projeto. A construtora $k$ ($1 \le k \le C$) cobra $B_k$ para construir cada aeroporto internacional e pode construir no máximo $H_k$ aeroportos internacionais. O custo das estradas não depende da construtora, e não há restrições quanto ao número ou ao comprimento das estradas. Para cada construtora, queremos saber o menor custo total para renovar a rede de transportes de modo a satisfazer as condições acima.

Algumas construtoras talvez não consigam realizar a renovação atendendo às condições, por poderem construir poucos aeroportos. Nesse caso, em vez do custo total, deve-se informar que não é possível satisfazer as condições.

Tarefa

Dados o inteiro $N$, que representa o número de cidades do país IOI, e suas coordenadas; o inteiro $M$, que representa o número de regiões onde não se pode construir estradas, e as coordenadas dessas regiões; e o inteiro $C$, que representa o número de construtoras candidatas, e as informações de cada uma delas, escreva um programa que determine, para cada construtora, o menor custo total para renovar a rede de transportes atendendo às condições do enunciado.

Entrada

Leia os seguintes dados da entrada padrão.

• A primeira linha contém três inteiros $N,M,C$, separados por espaços, que representam, respectivamente, o número de cidades do país IOI, o número de regiões onde não se pode construir estradas e o número de construtoras candidatas ao contrato.
• A linha $i$ ($1 \le i \le N$) das $N$ linhas seguintes contém dois inteiros $X_i,Y_i$, separados por um espaço, indicando que a cidade $i$ está no ponto $(X_i,Y_i)$.
• A linha $j$ ($1 \le j \le M$) das $M$ linhas seguintes contém quatro inteiros $P_j,Q_j,R_j,S_j$, separados por espaços. Eles indicam que o retângulo da região proibida $j$ tem canto inferior esquerdo $(P_j,Q_j)$ e canto superior direito $(R_j,S_j)$.
• A linha $k$ ($1 \le k \le C$) das $C$ linhas seguintes contém dois inteiros $B_k,H_k$, separados por um espaço. Isso significa que a construtora candidata $k$ cobra $B_k$ para construir cada aeroporto internacional e pode construir no máximo $H_k$ aeroportos internacionais.

Saída

Imprima $C$ linhas na saída padrão. A linha $k$ ($1 \le k \le C$) deve conter um inteiro que representa o menor custo total se a construtora candidata $k$ realizar o projeto. Entretanto, se essa construtora não conseguir realizar o projeto satisfazendo as condições, imprima o inteiro $-1$.

Restrições

Todos os dados de entrada satisfazem as seguintes condições.

• $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$).
• Não existem duas ou mais cidades nas mesmas 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$).
• Nenhuma região contém uma cidade em seu interior ou em sua borda.
• $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$).

Subtarefas

Subtarefa 1 [10 pontos]

As seguintes condições são satisfeitas.

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

Subtarefa 2 [30 pontos]

A seguinte condição é satisfeita.

• $C \le 100$.

Subtarefa 3 [30 pontos]

A seguinte condição é satisfeita.

• $M \le 100$.

Subtarefa 4 [30 pontos]

Não há restrições adicionais.

Exemplos

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

Saída 1

28
38
-1

Observação

O exemplo é ilustrado abaixo. Os retângulos de linhas grossas representam as regiões onde não se pode construir estradas.

É possível construir estradas ligando as cidades $2$ e $4$, e as cidades $3$ e $4$. Porém, não é possível construir uma estrada entre as cidades $1$ e $2$, pois ela atravessaria uma região proibida. Da mesma forma, não é possível construir uma estrada entre as cidades $1$ e $3$. Lembre-se de que uma estrada também não pode ter pontos em comum com a borda de um retângulo.

A primeira construtora pode construir até 4 aeroportos internacionais, ao custo de 7 por aeroporto. Nesse caso, a melhor solução é construir um aeroporto em cada cidade e nenhuma estrada. O custo total é $7\times4=28$.

A segunda construtora pode construir até 3 aeroportos internacionais, ao custo de 10 por aeroporto. Nesse caso, uma solução ótima é, por exemplo, construir estradas de comprimento $9$ ligando as cidades $2$ e $4$, e as cidades $3$ e $4$, e construir aeroportos internacionais nas cidades $1$ e $2$. O custo total é $10\times2+9+9=38$.

A terceira construtora pode construir no máximo 1 aeroporto internacional, ao custo de 1 por aeroporto. Entretanto, como não é possível construir uma estrada entre a cidade $1$ e qualquer outra cidade, são necessários pelo menos 2 aeroportos internacionais para satisfazer as condições do enunciado. Portanto, essa construtora não pode realizar o projeto, e imprimimos $-1$.