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$개의 국제공항을 건설할 수 있습니다 (도로를 건설하는 비용은 건설 회사에 따라 달라지지 않으며, 도로의 개수나 길이에 대한 제한은 없습니다). 각 건설 회사에 대해, 위 조건들을 만족하도록 교통망을 정비하는 데 필요한 최소 총비용을 구하고자 합니다.

건설할 수 있는 국제공항의 개수가 적기 때문에, 조건을 만족하면서 교통망을 정비할 수 없는 건설 회사가 있을 수도 있습니다. 그러한 경우에는 총비용 대신 조건을 만족할 수 없음을 보고해 주십시오.

문제

IOI 국가의 도시 개수를 나타내는 정수 $N$과 각 도시의 좌표, 도로를 건설할 수 없는 구역의 개수를 나타내는 정수 $M$과 각 구역의 좌표, 그리고 후보 건설 회사의 수를 나타내는 정수 $C$와 각 회사의 정보가 주어질 때, 문제 설명에 기술된 조건을 만족하면서 교통망을 정비하기 위해 각 건설 회사에 필요한 최소 총비용을 계산하는 프로그램을 작성하시오.

입력

표준 입력에서 다음 입력을 읽으시오:

• 첫 번째 줄에는 IOI 국가의 도시 개수, 도로를 건설할 수 없는 구역의 개수, 후보 건설 회사의 수를 각각 나타내는 세 정수 $N, M, C$가 공백으로 구분되어 주어집니다.
• 이어지는 $N$개의 줄 중 $i$번째 줄 ($1 \le i \le N$)에는 $i$번째 도시의 좌표 $(X_i, Y_i)$를 나타내는 두 정수 $X_i, Y_i$가 공백으로 구분되어 주어집니다.
• 이어지는 $M$개의 줄 중 $j$번째 줄 ($1 \le j \le M$)에는 도로를 건설할 수 없는 $j$번째 직사각형의 왼쪽 아래 점 $(P_j, Q_j)$와 오른쪽 위 점 $(R_j, S_j)$의 좌표를 나타내는 네 정수 $P_j, Q_j, R_j, S_j$가 공백으로 구분되어 주어집니다.
• 이어지는 $C$개의 줄 중 $k$번째 줄 ($1 \le k \le C$)에는 $k$번째 후보 건설 회사가 국제공항당 $B_k$의 비용이 들고 최대 $H_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 사이에도 도로를 건설할 수 없습니다 (도로는 직사각형의 경계와도 교차해서는 안 된다는 점에 유의하시오).

첫 번째 건설 회사는 각각 7의 비용으로 최대 4개의 국제공항을 건설할 수 있습니다. 이 경우 도로를 하나도 건설하지 않고 모든 도시에 국제공항을 건설하는 것이 최선이며, 총비용은 $7 \times 4 = 28$입니다.

두 번째 건설 회사는 각각 10의 비용으로 최대 3개의 국제공항을 건설할 수 있습니다. 이 경우 예를 들어 도시 2와 도시 4, 그리고 도시 3과 도시 4를 연결하는 길이 9인 도로들을 건설하고, 도시 1과 도시 2에 국제공항을 건설하는 것이 최선입니다. 총비용은 $10 \times 2 + 9 + 9 = 38$입니다.

세 번째 건설 회사는 각각 1의 비용으로 최대 1개의 국제공항을 건설할 수 있지만, 도시 1은 다른 어떤 도시로도 도로를 건설할 수 없으므로 문제 설명의 조건을 만족하려면 적어도 2개의 국제공항을 건설해야 합니다. 따라서 이 회사는 사업을 수행할 수 없음이 명백하므로 $-1$을 출력합니다.