005 - Intersection

問題

$N \ $個の区間が与えられます。区間$ \ i \ $は$ \ [l_i,r_i] \ $です。以下のような$ \ Q \ $個のクエリに答えてください。

• 区間$ \ [u,v] \ $と共通部分を持つような区間の個数を出力せよ。

なお、閉区間$ \ [X,Y] \ $とは$ \ X \ $以上$ \ Y \ $以下の全ての実数からなる区間です。

入力

入力は以下の形式で標準入力から与えられる。

$N \ Q$
$l_1 \ r_1$
$l_2 \ r_2$
$\vdots$
$l_N \ r_N$
$Query_1$
$Query_2$
$\vdots$
$Query_Q$

各クエリは以下の形式で与えられる。

$u \ v$

出力

各クエリに対する答えを改行区切りで出力せよ。

制約

• $1 \leq N,Q \leq 2 \times 10^5$
• $1 \leq l_i \leq r_i \leq 2 \times 10^5$
• $1 \leq u \leq v \leq 2 \times 10^5$
• 入力は全て整数

入出力例

入力例

3 3
3 5
1 4
6 6
2 3
2 2
7 9

出力例

2
1
0

1番目のクエリの場合、区間$ \ [2,3] \ $は$ \ 1,2 \ $番目の区間と共通部分を持つため$ \ 2 \ $を出力すればよいです。