В стране IOI решили полностью обустроить транспортную сеть. Страна представляется координатной плоскостью $xy$, на которой расположены $N$ городов. Город номер $i$ ($1 \le i \le N$) задаётся точкой $(X_i,Y_i)$. Обустройство сети проводится следующим образом.

• В некоторых из $N$ городов строятся международные аэропорты. Нужно построить хотя бы один аэропорт. Строительство каждого аэропорта имеет фиксированную стоимость.
• Строятся дороги между городами. Каждая дорога — отрезок, непосредственно соединяющий точки двух городов и параллельный оси $x$ или $y$. Стоимость строительства дороги равна её длине.

При этом должны выполняться следующие условия.

• В стране IOI есть $M$ областей, где нельзя строить дороги, например из-за плохого грунта. Каждая область — прямоугольник. У прямоугольника номер $j$ ($1 \le j \le M$) нижняя левая вершина — $(P_j,Q_j)$, а верхняя правая — $(R_j,S_j)$ (то есть $P_j<R_j$ и $Q_j<S_j$). Ни одна дорога не должна иметь общих точек ни с одной из $M$ областей. Граница входит в область, поэтому дорога не должна иметь общих точек даже с границей прямоугольника.
• Из каждого из $N$ городов должно быть возможно добраться до города с международным аэропортом, последовательно переходя по дорогам между городами.

На выполнение проекта претендуют $C$ строительных компаний. Компания номер $k$ ($1 \le k \le C$) строит один международный аэропорт за $B_k$ и может построить не более $H_k$ аэропортов. Стоимость строительства дорог не зависит от компании; число дорог и их длины не ограничены. Для каждой компании требуется найти минимальную общую стоимость обустройства транспортной сети с выполнением указанных условий.

Некоторые компании могут оказаться неспособны выполнить условия из-за слишком малого допустимого числа аэропортов. В таком случае вместо стоимости нужно сообщить о невозможности выполнения условий.

Задание

По числу городов $N$ и их координатам, числу запрещённых для дорог областей $M$ и координатам этих областей, числу компаний $C$ и информации о каждой компании напишите программу, вычисляющую для каждой компании минимальную общую стоимость обустройства транспортной сети с выполнением условий задачи.

Входные данные

Прочитайте следующие данные из стандартного ввода.

• Первая строка содержит три разделённых пробелами целых числа $N,M,C$ — соответственно число городов, число областей, где нельзя строить дороги, и число компаний-претендентов.
• Строка $i$ ($1 \le i \le N$) из следующих $N$ строк содержит два разделённых пробелом целых числа $X_i,Y_i$ — координаты $(X_i,Y_i)$ города $i$.
• Строка $j$ ($1 \le j \le M$) из следующих $M$ строк содержит четыре разделённых пробелами целых числа $P_j,Q_j,R_j,S_j$. Они задают нижнюю левую вершину $(P_j,Q_j)$ и верхнюю правую вершину $(R_j,S_j)$ прямоугольника запрещённой области $j$.
• Строка $k$ ($1 \le k \le C$) из следующих $C$ строк содержит два разделённых пробелом целых числа $B_k,H_k$. Компания $k$ строит один аэропорт за $B_k$ и может построить не более $H_k$ аэропортов.

Выходные данные

Выведите $C$ строк в стандартный вывод. Строка $k$ ($1 \le k \le C$) должна содержать одно целое число — минимальную общую стоимость выполнения проекта компанией $k$. Если компания $k$ не может выполнить проект с соблюдением условий, вместо стоимости выведите целое число -1.

Ограничения

Все входные данные удовлетворяют следующим условиям.

• $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$).
• Два или более города не имеют одинаковых координат.
• $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$).
• Ни одна область не содержит город ни внутри своего прямоугольника, ни на его границе.
• $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$).

Подзадачи

Подзадача 1 [10 баллов]

Выполняются следующие условия.

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

Подзадача 2 [30 баллов]

Выполняются следующие условия.

• $C \le 100$.

Подзадача 3 [30 баллов]

Выполняются следующие условия.

• $M \le 100$.

Подзадача 4 [30 баллов]

Дополнительных ограничений нет.

Примеры

Входные данные 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

Выходные данные 1

28
38
-1

Примечание

Этот пример изображён ниже. Прямоугольники с толстыми границами обозначают области, где нельзя строить дороги.

Можно построить дороги между городами $2$ и $4$, а также между городами $3$ и $4$. Но дорогу между городами $1$ и $2$ построить нельзя, поскольку она пересекла бы запрещённую область. Аналогично нельзя построить дорогу между городами $1$ и $3$. Помните, что дорога не должна иметь общих точек даже с границей прямоугольника.

Первая компания может построить не более 4 аэропортов стоимостью $7$ каждый. Оптимально не строить дороги, а построить аэропорт в каждом городе. Общая стоимость равна $7\times4=28$.

Вторая компания может построить не более 3 аэропортов стоимостью $10$ каждый. Например, оптимально построить дороги длины $9$ между городами $2$ и $4$ и между городами $3$ и $4$, а аэропорты — в городах $1$ и $2$. Общая стоимость равна $10\times2+9+9=38$.

Третья компания может построить не более одного аэропорта стоимостью $1$. Но город $1$ невозможно соединить дорогой ни с каким другим городом, поэтому для выполнения условий необходимо хотя бы два аэропорта. Эта компания не может выполнить проект, и нужно вывести -1.