Problem Description

Given a 2D plane, there are $n$ key points, $m$ rectangles, and $q$ queries. Each key point has a weight $a_i$.

A rectangle with bottom-left corner $(x_i,y_i)$ and top-right corner $(x'_i,y'_i)$ contains a point $(a,b)$ if and only if $x_i\le a\le x'_i$ and $y_i\le b\le y'_i$.

In each query, you are given $[l,r]$. For a key point $i$, if point $i$ lies in any rectangle whose index is within $[l,r]$, then we say that point $i$ is jointly contained by the rectangles in interval $[l,r]$. Output the sum of weights of all key points jointly contained by the rectangles in interval $[l,r]$.

Input Format

The first line contains an integer $n$.

Then follow $n$ lines, each containing two elements $p_i,a_i$, meaning the $i$-th key point is $(i,p_i)$ with weight $a_i$. It is guaranteed that $p$ is a permutation of $1$ to $n$.

Then one line contains an integer $m$.

Then follow $m$ lines, each containing four elements $x_i,x'_i,y_i,y'_i$, meaning the bottom-left corner of the $i$-th rectangle is $(x_i,y_i)$ and the top-right corner is $(x'_i,y'_i)$.

Then one line contains an integer $q$.

Then follow $q$ lines, each containing two elements $l,r$, meaning a query on interval $[l,r]$.

Output Format

For each query, output one line with one integer representing the answer.

10
6 4
2 3
4 3
10 8
8 8
9 9
7 3
1 9
5 7
3 7
10
1 3 2 5
3 7 8 10
3 4 3 6
3 4 5 7
6 8 1 8
4 9 6 9
1 5 6 9
4 9 2 7
1 1 1 5
1 1 4 9
10
2 6
7 8
2 8
6 9
9 10
4 5
5 6
3 7
7 10
1 2

40
22
51
31
4
12
29
36
22
31

Hint

Idea: nzhtl1477&ccz181078, Solution: zx2003, Code: ccz181078, Data: nzhtl1477.

Note: This problem uses bundled testdata. You can only get the score for a subtask after you pass all test points in that subtask.

For $5\%$ of the testdata, it is Sample 1.

For another $14\%$ of the testdata, $q=1$.

For another $19\%$ of the testdata, $n,m,q\leq 500$.

For another $19\%$ of the testdata, $n,m\leq 500$.

For another $19\%$ of the testdata, $n,m,q\leq 2000$.

For $100\%$ of the testdata, $1\leq n,m\leq 10^5$, $1\leq q \leq 10^6$.

$1\leq a_i \leq 10000$, $1\leq x_i\leq x_i'\leq n$, $1\leq y_i\leq y_i'\leq n$, $1\leq l\leq r\leq m$。

Translated by ChatGPT 5