IOI 国决定对交通网进行全面整修。IOI 国被表示为一个 $xy$ 坐标平面，上面有 $N$ 个城镇。第 $i$ 个城镇 ($1 \le i \le N$) 的坐标表示为 $(X_i, Y_i)$。交通网的整修按以下步骤进行：

• 在 $N$ 个城镇中的若干个城镇建设国际机场。必须至少建设 1 个国际机场。每建设一个国际机场都需要固定的成本。
• 铺设若干条连接城镇的道路。道路是直接连接城镇所在点的线段，且平行于 $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$ 个国际机场（铺设道路的成本与建筑公司无关，且对道路的数量和长度没有限制）。对于每家建筑公司，请计算其在满足上述条件的情况下，整修交通网所需的总成本的最小值。

由于可建设的国际机场数量有限，可能存在无法满足条件的建筑公司。在这种情况下，请报告该建筑公司无法满足条件，而不是输出总成本。

题目描述

给定 IOI 国的城镇数量 $N$ 及各城镇坐标、无法铺设道路的区域数量 $M$ 及各区域坐标、候选建筑公司的数量 $C$ 及各公司的信息，请编写一个程序，针对每家建筑公司，求出在满足题目所述条件的情况下，整修交通网所需的总成本的最小值。

输入格式

从标准输入读取以下内容：

• 第 1 行包含 3 个整数 $N, M, C$，分别表示 IOI 国的城镇数量、无法铺设道路的区域数量以及候选建筑公司的数量。
• 接下来的 $N$ 行中，第 $i$ 行 ($1 \le i \le N$) 包含 2 个整数 $X_i, Y_i$，表示第 $i$ 个城镇的坐标为 $(X_i, Y_i)$。
• 接下来的 $M$ 行中，第 $j$ 行 ($1 \le j \le M$) 包含 4 个整数 $P_j, Q_j, R_j, S_j$，表示第 $j$ 个无法铺设道路的区域长方形的左下角坐标为 $(P_j, Q_j)$，右上角坐标为 $(R_j, S_j)$。
• 接下来的 $C$ 行中，第 $k$ 行 ($1 \le k \le C$) 包含 2 个整数 $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