У країні IOI вирішили одночасно розбудувати транспортну мережу. Країну 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$, що задає кількість міст країни IOI, і координати цих міст, ціле число $M$, що задає кількість областей, у яких неможливо прокладати дороги, і координати цих областей, а також ціле число $C$, що задає кількість компаній, які претендують на виконання проєкту, та інформацію про кожну компанію, напишіть програму, яка для кожної компанії знаходить мінімальну сумарну вартість розбудови транспортної мережі з виконанням умов задачі.

Вхідні дані

Прочитайте зі стандартного вводу такі дані.

• У першому рядку записано три цілі числа $N,M,C$, розділені пробілами. Вони задають відповідно кількість міст країни IOI, кількість областей, у яких неможливо прокладати дороги, і кількість компаній, які претендують на виконання проєкту.
• У рядку $i$ ($1 \le i \le N$) із наступних $N$ рядків записано два цілі числа $X_i,Y_i$, розділені пробілом. Вони означають, що координати міста $i$ — $(X_i,Y_i)$.
• У рядку $j$ ($1 \le j \le M$) із наступних $M$ рядків записано чотири цілі числа $P_j,Q_j,R_j,S_j$, розділені пробілами. Вони означають, що нижня ліва вершина прямокутника, який задає область $j$, у якій неможливо прокладати дороги, має координати $(P_j,Q_j)$, а верхня права — $(R_j,S_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 \times 4=28$.

Друга компанія може побудувати не більше ніж 3 міжнародні аеропорти вартістю 10 за кожний. У цьому разі, наприклад, найкраще прокласти дороги довжини 9 між містами 2 і 4 та між містами 3 і 4, а також побудувати міжнародні аеропорти в містах 1 і 2; сумарна вартість становитиме $10 \times 2+9+9=38$.

Третя компанія може побудувати не більше ніж 1 міжнародний аеропорт вартістю 1. Але оскільки між містом 1 і будь-яким іншим містом неможливо прокласти дорогу, для виконання умов задачі необхідно побудувати принаймні 2 міжнародні аеропорти. Отже, ця компанія не може виконати проєкт, тому виводиться $-1$.