AT_abc365_g [ABC365G] AtCoder Office

[problemUrl]: https://atcoder.jp/contests/abc365/tasks/abc365_g 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 $ 番目の質問に対する答えを出力せよ。

### 制約 - $ 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) $ - 入力はすべて整数 ### Sample Explanation 1 $ 3 $ 人の高橋くんがオフィスの中にいた時間はそれぞれ以下の図のようになります。 !\[\](https://img.atcoder.jp/abc365/268561b2e39007a186ef6ce29471170f.png) それぞれの質問に対する答えは以下のようになります。 - $ 1 $ 番目の高橋くんと $ 2 $ 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 $ 20 $ から時刻 $ 30 $ の間と時刻 $ 70 $ から時刻 $ 80 $ の間の $ 2 $ 回です。長さはどちらも $ 10 $ なので、これらの合計である $ 20 $ を出力してください。 - $ 1 $ 番目の高橋くんと $ 3 $ 番目の高橋くんが同時にオフィスの中にいたことはありません。よって、$ 0 $ を出力してください。 - $ 2 $ 番目の高橋くんと $ 3 $ 番目の高橋くんが同時にオフィスの中にいた時間は、時刻 $ 40 $ から時刻 $ 60 $ の間の $ 1 $ 回です。長さは $ 20 $ なので、$ 20 $ を出力してください。