#CS1664. 电影节查询

电影节查询

题目背景

翻译自 CSES-1664 题。

题目描述

在一个电影节中，将会放映 n 部电影。你知道每部电影的开始时间和结束时间。

你的任务是处理 q 个查询，每个查询的形式是：如果你在特定的时间到达并离开电影节，那么你最多能看多少部电影？

你可以观看两部电影，如果第一部电影的结束时间不晚于第二部电影的开始时间。你可以在到达时开始第一部电影，并且在最后一部电影结束时离开。

输入格式

第一行包含两个整数 n 和 q，分别表示电影的数量和查询的数量。

接下来有 n 行，每行包含两个整数 a 和 b，表示一部电影的开始时间和结束时间。

最后有 q 行，每行包含两个整数 a 和 b，表示你的到达时间和离开时间。

输出格式

对于每个查询，输出一个整数：表示你能观看的最多电影数量。

样例

4 3
2 5
6 10
4 7
9 10
5 9
2 10
7 10

0
2
1

说明/提示

$1 \leq n, q \leq 2 \times 10^5$

1 \leq a < b \leq 10^6