問題
$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 \ $を出力すればよいです。