AtCoder 办公室

题目描述

有 $N$ 人在 AtCoder 办公室工作。

办公室记录员工的进出，自记录开始以来共有 $M$ 次进出。

第 $i$ 条（$1\leq i\leq M$）记录由一对整数 $(T_i, P_i)$ 表示，表示在时刻 $T_i$，第 $P_i$ 个人如果当时在外面则进入办公室，如果当时在里面则离开办公室。

已知记录开始时所有人都在办公室外面，并且现在他们也在外面。

请回答 $Q$ 个如下格式的询问。

对于第 $i$ 个（$1\leq i\leq Q$）询问，给定一对整数 $(A_i, B_i)$。求自记录开始以来，第 $A_i$ 个人和第 $B_i$ 个人同时在办公室内的时段的总长度。

输入格式

输入按以下格式从标准输入给出。

$N$ $M$
$T_1$ $P_1$
$T_2$ $P_2$
$\vdots$
$T_M$ $P_M$
$Q$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_Q$ $B_Q$

输出格式

输出 $Q$ 行。第 $i$ 行（$1\leq i\leq Q$）输出第 $i$ 个询问的答案。

样例

3 8
10 1
20 2
30 1
40 3
60 3
70 1
80 2
90 1
3
1 2
1 3
2 3

20
0
20

下图显示了这三个人各自在办公室内的时间。

各个询问的答案如下：

第 1 个人和第 2 个人在时刻 $20$ 到 $30$ 之间以及时刻 $70$ 到 $80$ 之间同时在办公室内。这两段时段的长度都为 $10$，所以输出总和 $20$。

第 1 个人和第 3 个人从未同时待在办公室内，所以输出 $0$。

第 2 个人和第 3 个人在时刻 $40$ 到 $60$ 之间同时在办公室内。该时段的长度为 $20$，所以输出 $20$。

10 20
10257 9
10490 4
19335 1
25893 5
32538 9
33433 3
38522 9
40629 9
42896 5
52106 1
53024 3
55610 5
56721 9
58286 9
63128 3
70513 3
70977 4
74936 5
79883 9
95116 9
7
1 3
3 9
1 9
4 9
1 5
5 9
3 5

18673
2107
15310
25720
17003
10317
16848

数据范围

• $2\leq N\leq2\times10^5$
• $2\leq M\leq2\times10^5$
• $1\leq T_1\lt T_2\lt\dotsb\lt T_M\leq10^9$
• $1\leq P_i\leq N\ (1\leq i\leq M)$
• 对于每个 $1\leq p\leq N$，满足 $P_i=p$ 的下标 $i$ 的数量为偶数
• $1\leq Q\leq2\times10^5$
• $1\leq A_i\lt B_i\leq N\ (1\leq i\leq Q)$
• 所有输入均为整数