当前没有测试数据。

题目描述

在一个圆上等距分布着 $2N$ 个点，顺时针编号为 $1,2,\cdots,2N$。$2N$ 顺时针方向的下一个点是 $1$。

接下来圆上出现了 $M$ 条线段，第 $i$ 条线段的两个端点分别为 $A_i$ 和 $B_i$，并且这两个端点的编号是偶数。保证不会有两条线段共享一个端点。

接下来你要回答 $Q$ 个询问，每次询问给出两个奇数 $C_j,D_j$，你要回答如果圆上新增了一条线段，两个端点分别是 $C_j,D_j$，那么这条新线段会和原有的 $M$ 条线段中的多少条相交。

输入格式

第一行两个整数 $N,M(2\le N\le 10^6,1\le M\le \min(\left\lfloor\frac{N}{2}\right\rfloor,2\times 10^5))$。

接下来 $M$ 行，每行两个整数 $A_i,B_i(1\le A_i<B_i\le 2N,A_i,B_i\bmod2=0)$，表示圆上的线段。保证这 $M$ 条线段中没有两条存在交点。

接下来一行一个整数 $Q(1\le Q\le 2\times 10^5)$。

接下来 $Q$ 行每行两个整数 $C_j,D_j(1\le C_j<D_j\le 2N,C_j,D_j\bmod 2=1)$，表示一次询问。

输出格式

输出 $Q$ 行，每行一个整数依次回答询问。

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

1
2
0

20 7
24 34
26 28
18 38
2 14
8 12
30 32
20 22
10
7 29
31 39
9 21
19 29
15 21
11 39
17 21
15 31
5 25
25 31

3
3
4
1
2
2
2
3
3
1

说明/提示

样例 1 解释

如下图：

黑点表示圆上的 $2N$ 个点，蓝线为 $M$ 条线段，第 $i$ 条称线段 $i$；红线表示询问，第 $i$ 个对应的线段称询问 $i$。

• 第一次询问中，和询问 $1$ 相交的线段为线段 $1$；
• 第二次询问中，和询问 $2$ 相交的线段有线段 $1,2$；
• 第三次询问中，没有线段和询问 $3$ 相交。