AT_ndpc2026_e 夏休み

あなたは今日から夏休みです。夏休みは $ N $ 日間からなります。 $ M $ 個のイベントがあります。 $ i $ 個目のイベントは $ A_i $ 日目の朝にはじまって $ B_i $ 日目の夜に終わります。 $ Q $ 個のクエリに答えてください。クエリでは $ L, R $ が与えられるので、次の問いに答えてください。 > あなたは $ L $ 日目から $ R $ 日目の間にできるだけたくさんのイベントに参加することにしました。 > ただし、イベントは途中参加や途中抜けが出来ません。よって期間が被っている複数のイベントに参加したり、 $ L $ 日目より前や $ R $ 日目より後を期間に含むイベントに参加することはできません。 > 参加するイベントを上手く選んだ時、最大で何個のイベントに参加できますか？

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_M $ $ B_M $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリは以下の形式で与えられる。 > $ L $ $ R $

$ Q $ 行出力せよ。 $ i $ 行目には $ i $ 番目のクエリへの答えを出力せよ。

### Sample Explanation 1 例えば $ 1 $ 番目のクエリでは、 $ 1 $ 番目のイベントと $ 2 $ 番目のイベントに参加することが出来てこれが最大です。 ### Constraints - $ 1 \leq N \leq 2 \times 10^5 $ - $ 1 \leq M \leq 2 \times 10^5 $ - $ 1 \leq Q \leq 2 \times 10^5 $ - $ 1 \leq A_i \leq B_i \leq N $ - $ 1 \leq L \leq R \leq N $ - 入力される値は全て整数