AT_ndpc2026_e 夏休み

Your summer vacation starts today and lasts for $ N $ days. There are $ M $ events. The $ i $ -th event starts on the morning of day $ A_i $ and ends on the evening of day $ B_i $ . You are given $ Q $ queries. In each query, you are given two integers $ L $ and $ R $ , and you need to answer the following: > You decide to attend as many events as possible during the period from day $ L $ to day $ R $ . > However, you cannot join or leave an event in the middle. Therefore, you cannot attend multiple events whose time periods overlap, and you also cannot attend any event that starts before day $ L $ or ends after day $ R $ . > If you choose the events optimally, what is the maximum number of events you can attend?

The input is given from standard input in the following format: > $ 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 $ Each query is given in the following format: > $ L $ $ R $

Print $ Q $ lines. For the $ i $ -th line, output the answer to the $ i $ -th query.

### Sample Explanation 1 For example, in the first query, you can attend the 1st and 2nd events, and this is the maximum. ### 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 $ - All input values are integers