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$.

Each query provides a range $[l, r]$. A key point $i$ is considered to be contained by the union of rectangles in the range $[l, r]$ if it is contained in at least one rectangle with an index in $[l, r]$. Output the sum of weights of all key points contained by the union of rectangles in the range $[l, r]$.

Input

The first line contains an integer $n$.

The next $n$ lines each contain two integers $p_i$ and $a_i$, representing the $i$-th key point at $(i, p_i)$ with weight $a_i$. It is guaranteed that $p$ is a permutation of $1$ to $n$.

The next line contains an integer $m$.

The next $m$ lines each contain four integers $x_i, x'_i, y_i, y'_i$, representing the $i$-th rectangle with bottom-left corner $(x_i, y_i)$ and top-right corner $(x'_i, y'_i)$.

The next line contains an integer $q$.

The next $q$ lines each contain two integers $l$ and $r$, representing a query for the range $[l, r]$.

Output

For each query, output a single integer representing the answer on a new line.

Examples

Input 1

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

Output 1

40
22
51
31
4
12
29
36
22
31

Subtasks

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

Note: This problem uses bundled testing. You will only receive points for a subtask if you pass all test cases within that subtask.

For $5\%$ of the data, the input is the sample case.

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

For another $19\%$ of the data, $n, m, q \le 500$.

For another $19\%$ of the data, $n, m \le 500$.

For another $19\%$ of the data, $n, m, q \le 2000$.

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

$1 \le a_i \le 10000$, $1 \le x_i \le x'_i \le n$, $1 \le y_i \le y'_i \le n$, $1 \le l \le r \le m$.