건설 사업

IOI 나라에서는 교통망을 한꺼번에 정비하려고 한다. IOI 나라는 xy 좌표 평면으로 나타내며, 그 위에 $N$개의 마을이 있다. $i$번째 ($1 \le i \le N$) 마을은 점 $(X_i, Y_i)$로 나타낸다. 교통망 정비는 다음 순서로 진행한다.

• $N$개의 마을 중 몇 개에 국제공항을 건설한다. 국제공항은 적어도 1개는 건설해야 한다. 국제공항은 1개를 건설할 때마다 정해진 비용이 든다.
• 마을끼리 잇는 도로를 몇 개铺设한다. 도로는 마을을 나타내는 점끼리 직접 잇는, $x$축 또는 $y$축에 평행한 선분이며, 도로는 1개를铺设할 때마다 그 길이만큼의 비용이 든다.

이때 다음 조건을 만족해야 한다.

• 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$) 건설회사는 국제공항을 1개 건설하는 데 비용 $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$번째 발주처 후보 건설회사가 국제공항을 1개 건설하는 데 $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$).
• 같은 좌표에 마을이 2개 이상 있는 경우는 없다.
• $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$).