BUS hard(400)

問題文

とあるバスの路線には、$N$ 個のバス停があり、毎日 $M$ 人の客が乗車している。具体的には、$i$ $(1 \leq i \leq M)$ 人目の客は始発のバス停から数えて $l_i$ 番目のバス停で乗車し、 $r_i$ 番目のバス停で降車する。このとき、次の $Q$ 個のクエリに答えよ。クエリ中の $i$ $(1 \leq i \leq Q)$ はそのクエリが何番目のクエリかを示す。

• 始発のバス停から数えて $B_i$ 番目のバス停から $E_i$ 番目のバス停までの間にのみバスに乗車している人数を答えよ。 つまり、$B_i \leq l_j < r_j \leq E_i$ を満たすような $j$ $(1 \leq j \leq M)$ の個数を求めよ。

制約

• $2 \leq N \leq 2 \times 10^3$
• $1 \leq M \leq 2 \times 10^5$
• $1 \leq l_i < r_i \leq N$ $(1 \leq i \leq M)$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq B_i < E_i \leq N$ $(1 \leq i \leq Q)$

入力

入力はすべて整数である。

N M
l_1 r_1
l_2 r_2
...
l_M r_M
Q
B_1 E_1
B_2 E_2
...
B_Q E_Q

出力

各クエリについて、答えを1行づつ出力せよ。

サンプル

 4 3
 1 4
 2 3
 1 3
 3
 1 3
 1 4
 1 2

2
3
0

例えば1つ目のクエリでは、1番目から3番目のバス停の間にのみ乗っていた乗客の人数を答えます。1人目の乗客は4番目のバス停まで乗っていたため含まれず、残りの2人は含まれます。2人目の乗客のように、各クエリで指定された区間の中にバスに乗車していない区間が含まれていても乗車していた区間が指定された区間の中に収まっていればカウントされることに注意してください。

5 5
1 2
2 3
3 4
4 5
1 5
4
1 3
2 4
3 5
1 5

2
2
2
5