The country of IOI has decided to carry out a comprehensive development of its transportation network. IOI is represented as an $xy$-coordinate plane, on which there are $N$ towns. The $i$-th town ($1 \le i \le N$) is represented as a point $(X_i, Y_i)$. The development of the transportation network is carried out according to the following procedure:

• Construct international airports in some of the $N$ towns. At least one international airport must be constructed. Each international airport constructed incurs a fixed cost.
• Construct several roads connecting towns. A road is a line segment parallel to the $x$-axis or $y$-axis that directly connects two points representing towns. Each road constructed incurs a cost equal to its length.

At this time, the following conditions must be satisfied:

• There are $M$ regions in IOI where roads cannot be constructed due to poor ground conditions or other reasons. Each region is represented as a rectangle; the $j$-th rectangle ($1 \le j \le M$) has its bottom-left corner at $(P_j, Q_j)$ and its top-right corner at $(R_j, S_j)$ (where $P_j < R_j$ and $Q_j < S_j$). No road may have any intersection with any of the $M$ regions. The regions include their boundaries, and no road may have any intersection with the boundary of any rectangle representing a region.
• It must be possible to reach a town with an international airport from any of the $N$ towns by repeatedly traveling along roads to other towns.

Construction company $C$ is a candidate for this project. The $k$-th construction company ($1 \le k \le C$) incurs a cost of $B_k$ to construct one international airport and can construct at most $H_k$ international airports (the cost of constructing roads does not depend on the construction company, and there are no restrictions on the number or length of roads). For each construction company, we want to find the minimum total cost to develop the transportation network such that the above conditions are satisfied.

Since the number of international airports that can be constructed is small, there may be construction companies that cannot develop the transportation network while satisfying the conditions. In such cases, please report that the conditions cannot be satisfied instead of the total cost.

Task

Given the integer $N$ representing the number of towns in IOI and their coordinates, the integer $M$ representing the number of regions where roads cannot be constructed and their coordinates, and the integer $C$ representing the number of candidate construction companies and their information, write a program that calculates the minimum total cost for each construction company to develop the transportation network while satisfying the conditions described in the problem statement.

Input

Read the following input from standard input:

• The first line contains three integers $N, M, C$, separated by spaces, representing the number of towns in IOI, the number of regions where roads cannot be constructed, and the number of candidate construction companies, respectively.
• The $i$-th line of the following $N$ lines ($1 \le i \le N$) contains two integers $X_i, Y_i$, separated by spaces, representing the coordinates $(X_i, Y_i)$ of the $i$-th town.
• The $j$-th line of the following $M$ lines ($1 \le j \le M$) contains four integers $P_j, Q_j, R_j, S_j$, separated by spaces, representing the coordinates of the bottom-left point $(P_j, Q_j)$ and the top-right point $(R_j, S_j)$ of the $j$-th rectangle where roads cannot be constructed.
• The $k$-th line of the following $C$ lines ($1 \le k \le C$) contains two integers $B_k, H_k$, separated by spaces, representing that the $k$-th candidate construction company incurs a cost of $B_k$ per international airport and can construct at most $H_k$ international airports.

Output

Output $C$ lines to standard output. The $k$-th line ($1 \le k \le C$) should contain a single integer representing the minimum total cost for the $k$-th candidate construction company to carry out this project. However, if the $k$-th candidate construction company cannot carry out the project while satisfying the conditions, output $-1$ instead.

Constraints

All input data satisfy the following conditions:

• $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 two towns are at the same coordinates.
• $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$).
• No region contains a town in its interior or on its boundary.
• $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$).

Subtasks

Subtask 1 [10 points]

Satisfies the following conditions: $M \le 100$. $C \le 100$.

Subtask 2 [30 points]

Satisfies the following condition: * $C \le 100$.

Subtask 3 [30 points]

Satisfies the following condition: * $M \le 100$.

Subtask 4 [30 points]

No additional constraints.

Examples

Input 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

Output 1

28
38
-1

Note

The example input can be illustrated as follows. The rectangles with thick lines indicate the regions where roads cannot be constructed.

Although it is possible to construct roads connecting Town 2 and Town 4, and Town 3 and Town 4, it is not possible to construct a road between Town 1 and Town 2 because it would intersect a region where roads cannot be constructed. Similarly, it is not possible to construct a road between Town 1 and Town 3 (note that roads must not have any intersection with the boundaries of the rectangles).

The first construction company can construct at most 4 international airports at a cost of 7 each. In this case, it is best to construct international airports in all towns without constructing any roads, and the total cost is $7 \times 4 = 28$.

The second construction company can construct at most 3 international airports at a cost of 10 each. In this case, it is best to construct, for example, roads of length 9 connecting Town 2 and Town 4, and Town 3 and Town 4, and construct international airports at Town 1 and Town 2. The total cost is $10 \times 2 + 9 + 9 = 38$.

The third construction company can construct at most 1 international airport at a cost of 1 each, but since Town 1 cannot have a road constructed to any other town, at least 2 international airports must be constructed to satisfy the conditions in the problem statement. Thus, it is clear that this company cannot carry out the project, so we output $-1$.