题目描述

给定一个二维平面，有 $n$ 个关键点，$m$ 个矩形，以及 $q$ 个询问，每个关键点有一个权值 $a_i$。

定义一个左下角为 $(x_i,y_i)$，右上角为 $(x'_i,y'_i)$ 的矩形包含一个点 $a,b$，当且仅当 $x_i\le a\le x'_i$ 且 $y_i\le b\le y'_i$。

每次询问给定 $[l,r]$，对于一个关键点 $i$ ，如果点 $i$ 在编号在 $[l,r]$ 内的任意一个矩形中，则认为 $i$ 被区间 $[l,r]$ 的矩形并包含，输出区间 $[l,r]$ 的矩形并包含的所有关键点的权值和。

输入格式

第一行一个数 $n$。

之后 $n$ 行每行两个元素 $p_i,a_i$，表示第 $i$ 个关键点 $(i,p_i)$，权值为 $a_i$，保证 $p$ 为一个 $1$ 到 $n$ 的排列。

之后一行一个数 $m$。

之后 $m$ 行每行四个元素 $x_i,x'_i,y_i,y'_i$，表示第 $i$ 个矩形左下角为 $(x_i,y_i)$，右上角为 $(x'_i,y'_i)$。

之后一行一个数 $q$。

之后 $q$ 行每行两个元素 $l,r$，表示一次对区间 $[l,r]$ 的询问。

输出格式

对于每次询问，输出一行一个数表示答案。

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

提示

Idea：nzhtl1477&ccz181078，Solution：zx2003，Code：ccz181078，Data：nzhtl1477

注意：本题采用捆绑测试，只有当你通过一个 subtask 中的所有测试点后，你才能拿到这个 subtask 的分数。

对于其中 $5\%$ 的数据，为样例 1。

对于另外 $14\%$ 的数据，$q=1$。

对于另外 $19\%$ 的数据，$n,m,q\leq 500$。

对于另外 $19\%$ 的数据，$n,m\leq 500$。

对于另外 $19\%$ 的数据，$n,m,q\leq 2000$。

对于 $100\%$ 的数据，$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$。