题目描述

昨天，$N$ 位顾客光顾了 EGOI 自助餐厅。顾客编号从 $1$ 到 $N$，顾客 $i(1\le i\le N)$ 到达时间为 $L_i$，离开时间为 $R_i$。今天，我们发现有一位顾客来店时感染了目前在 JOI 国流行的新型传染病 X。

传染病 X 的传染性用整数 $x$ 表示。具体来说，对于 $1\le i\le N$，当顾客 $i$ 与一个或多个感染者同时进入餐厅的累计总时间至少达到 $x$ 时，顾客 $i$ 就会成为新感染者。

现在，由于 JOI 国采取了严格的感染控制措施，因此必须确定感染者人数。然而，问题在于调查组并不知道哪些人感染了传染病，而代表传染性的整数 $x$ 的值也是未知数。

因此，EGOI 自助餐厅经理理惠决定对于 $Q$ 种情况，分别求出最终会有多少顾客被感染。在第 $j(1\le j\le Q)$ 种情况下，最初只有顾客 $P_j$ 受到感染，传染性为 $X_j$。

根据到店顾客的信息，求出每种情况下最终的感染人数。注意，即使受感染的人数是在他们离开餐厅时被感染的，也应包括在内。此外，还假定一旦顾客感染了传染病 X，他就不能再被感染。

输入格式

第一行输入一个整数 $N$。

接下来 $N$ 行，每行两个整数 $L_i,R_i$。

接下来一行输入一个整数 $Q$。

接下来 $Q$ 行，每行两个整数 $P_i,X_i$。

输出格式

输出 $Q$ 行，第 $j(1\le j\le Q)$ 行一个整数表示第 $j$ 种情况下的最终感染人数。

输入输出样例 #1

4
10 40
20 80
45 60
70 95
1
1 15

3

输入输出样例 #2

8
0 30
0 90
0 80
0 60
0 20
0 40
0 70
0 50
3
1 30
1 40
4 50

7
1
5

输入输出样例 #3

5
0 10
0 10
0 10
0 10
0 10
4
1 9
1 10
1 11
1 1000000000

5
5
1
1

输入输出样例 #4

7
38 61
13 27
10 54
22 56
49 75
27 47
70 99
1
3 10

6

输入输出样例 #5

10
10 20
11 21
13 23
16 26
20 30
25 35
31 41
38 48
46 56
80 90
4
1 3
1 6
1 8
1 10

8
5
3
1

输入输出样例 #6

7
10 54
38 61
13 27
22 56
49 75
27 47
70 99
5
1 3
1 6
1 9
1 12
1 15

7
6
6
6
4

输入输出样例 #7

7
38 61
13 27
10 54
22 56
49 75
27 47
70 99
5
1 10
2 10
3 10
4 10
5 10

4
6
6
5
2

说明/提示

【样例解释 #1】

在第 $1$ 个询问中，初始的感染者是顾客 $1$，传染性为 $15$，因此感染的传播方式如下

• 在时间 $10$，顾客 $1$ 到达餐厅；
• 在时间 $20$，顾客 $2$ 到达餐厅；
• 在时间 $35$，顾客 $2$ 与顾客 $1$ 同时出现在餐厅累计时间为 $15$，顾客 $2$ 被感染；
• 在时间 $40$，顾客 $1$ 离开餐厅；
• 在时间 $45$，顾客 $3$ 到达餐厅；
• 在时间 $60$，顾客 $3$ 与顾客 $2$ 同时出现在餐厅累计时间为 $15$，顾客 $3$ 被感染；与此同时，顾客 $3$ 离开餐厅；
• 在时间 $70$，顾客 $4$ 到达餐厅；
• 在时间 $80$，顾客 $2$ 离开餐厅；
• 在时间 $95$，顾客 $4$ 与顾客 $2$ 同时出现在餐厅累计时间为 $10$，因此顾客 $4$ 未感染；与此同时，顾客 $4$ 离开餐厅。

最终顾客 $1,2,3$ 被感染，共 $3$ 人，故第 $1$ 个询问答案为 $3$。

该样例满足子任务 $4,5,6,8,9,10$ 的限制。

【样例解释 #2】

• 在第 $1$ 个询问中，$7$ 个顾客 $1,2,3,4,6,7,8$ 最终被感染，答案为 $7$。
• 在第 $2$ 个询问中，$1$ 个顾客 $1$ 最终被感染，答案为 $1$。
• 在第 $3$ 个询问中，$5$ 个顾客 $2,3,4,7,8$ 最终被感染，答案为 $5$。

该样例满足子任务 $2,3,4,5,6,10$ 的限制。

【样例解释 #3】

该样例满足子任务 $1,2,3,5,6,8,10$ 的限制。

【样例解释 #4】

该样例满足子任务 $4,5,6,9,10$ 的限制。

【样例解释 #5】

该样例满足子任务 $4,5,6,7,8,9,10$ 的限制。

【样例解释 #6】

该样例满足子任务 $4,5,6,7,8,10$ 的限制。

【样例解释 #7】

该样例满足子任务 $4,5,6,7,9,10$ 的限制。

【数据范围】

• $1\le N\le 10^5$；
• $0\le L_i\lt R_i\le 10^9(1\le i\le N)$；
• $1\le Q\le 10^5$；
• $1\le P_j\le N(1\le j\le Q)$；
• $1\le X_j\le 10^9(1\le j\le Q)$。

【子任务】

1. （$2$ 分）$L_i=0(1\le i\le N)$，$R_i=10(1\le i\le N)$，$Q\le 5$；
2. （$3$ 分）$L_i=0(1\le i\le N)$，$Q\le 5$；
3. （$6$ 分）$L_i=0(1\le i\le N)$；
4. （$10$ 分）$N\le 500$，$Q\le 5$，$R_i\le 500(1\le i\le N)$，$X_j\le 500(1\le j\le Q)$；
5. （$11$ 分）$N\le 500$，$Q\le 5$；
6. （$16$ 分）$Q\le 5$；
7. （$13$ 分）$P_j=1(1\le j\le Q)$，$L_1\lt L_2\lt \cdots\lt L_N$，$R_1\lt R_2\lt \cdots\lt R_N$；
8. （$14$ 分）$P_j=1(1\le j\le Q)$；
9. （$15$ 分）$R_i-L_i(1\le i\le N)$ 的最小值大于或等于 $X_j(1\le j\le Q)$ 的最大值；
10. （$10$ 分）无附加限制。