思路与证明

把每个细菌看成平面上的点 $(l_i,r_i)$。一个查询 $[l,r]$ 的条件是 $l_i\ge l$ 且 $r_i\le r$，等价于统计矩形 $[l,+\infty)\times(-\infty,r]$ 中的点数。这是典型的二维偏序计数。

离线做法：

1. 将所有细菌按 $r_i$ 升序排序；将所有查询按 $r$ 升序排序。
2. 依次处理查询的 $r$，把所有满足 $r_i\le r$ 的细菌“加入”数据结构。
3. 数据结构只按 $l_i$ 这一维统计：我们想要的是“当前已加入的点里，$l_i\ge l$ 的数量”。

题目内容

小C 在实验室中培育了 $n$ 个细菌。

第 $i$ 个细菌的生命周期用一个闭区间 $[l_i,r_i]$ 表示。

现有 $m$ 次查询，每次查询给出一个时间区间 $[l,r]$ 。

对于每次查询，请计算生命周期完全位于该区间内即 $(l ≦l_i$ 且 $r_i ≦r)$ 的细菌数量。

输入描述

第一行输入两个整数 $n$ 和 $m(1≦n,m ≦5×10^5)$ ，分别表示细菌的数量和查询次数。

接下来 $n$ 行，每行输入两个整数 $l_i$ 和 $r_i(1≦l_i≦r_i≦ 10^9)$ ，表示第 $i$ 个细菌的生命周期区间。

随后 $m$ 行，每行输入两个整数 $l$ 和 $r(1 ≦l≦r≦ 10^9)$ ，表示一次查询的时间区间。

输出描述

输出 $m$ 行，每行输出一个整数，表示对应查询的答案。

样例1

输入

5 3
1 2
2 5
3 4
1 10
6 8
1 5
2 6
1 10

输出

3
2
5

说明

• 共有 $5$ 个细菌，其生命周期区间分别为：

  • 第 $1$ 个：$[1,2]$ ；
  • 第 $2$ 个：$[2,5]$ ；
  • 第 $3$ 个：$[3,4]$ ；
  • 第 $4$ 个：$[1,10]$ ；
  • 第 $5$ 个：$[6,8]$ 。

• 查询区间 $[1,5]$ 时，有 $3$ 个细菌(第 $1、2、3$ ) 的生命周期完全在该区间内，故输出 $3$ ；

• 查询区间 $[2,6]$ 时，有 $2$ 个细菌(第 $2、3$ )满足条件，故输出 $2$ ；

• 查询区间 $[1,10]$ 时，所有 $5$ 个细菌都满足条件，故输出 $5$ 。

样例2

输入

4 2
1 3
2 4
3 5
4 6
2 4
3 6

输出

1
2