题目描述

给定数轴上的 $n$ 个区间 $[l, r]$。

有 $m$ 次询问，每次询问给你一个区间 $[x, y]$，你需要回答出最少需要从给定的区间内选出多少个区间能使选择的区间的并集是覆盖区间 $[x, y]$ 的。
$\Rightarrow$ 这也就是说，设你选择的最少的区间的并集为 $A$，则 $[x, y] \subseteq A$。

注意：我们这里说的区间指的都是数轴上面的线段，你选择的区间不仅仅需要覆盖区间范围内整数的点，还要覆盖所有非整数的点。比如：$[x, y] = [3, 5]$，而你选择了两个给定的区间 $[1, 3]$ 和 $[4, 5]$，则这两个给定的区间的并集并没有完全包含区间 $[3, 5]$ 内的所有的点，在 $(3, 4)$ 范围内的点，比如 $3.3$，是满足 $3.3 \in [3, 5]$ 的，但是 $3.3 \notin [1, 3] \cup [4, 5]$

输入格式

输入的第一行包含两个整数 $n$ 和 $m$，以一个空格分隔（$1 \le n, m \le 2 \cdot 10^5$），分别表示给定的区间的数量，以及询问次数。

接下来 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \lt r_i \le 5 \cdot 10^5$），表示每个给定的区间。

接下来 $m$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$0 \le x_i \lt y_i \le 5 \cdot 10^5$），表示一次询问。

输出格式

对于每次询问的 $[x_i, y_i]$，输出一行，包含一个整数，表示从给定的 $n$ 个区间内至少选择几个区间能使 $[x_i, y_i]$ 完全包含在选择的这些区间的并集中；如果选择了所有的区间都无法完全包含 $[x_i, y_i]$，则这个数字对应为 $-1$。

样例输入1

2 3
1 3
2 4
1 3
1 4
3 4

样例输出1

1
2
1

样例输入2

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

样例输出2

1
1
-1
-1

说明/提示

样例解释

样例1：

1. 询问 $[1, 3]$ 可以被区间 $[1, 3]$ 覆盖；
2. 询问 $[1, 4]$ 可以被区间 $[1, 3] \cup [2, 4]$ 覆盖（没有办法用一个给定的区间就覆盖 $[1, 4]$）；
3. 询问 $[3, 4]$ 可以被区间 $2, 4$ 覆盖。

样例2：

1. 询问 $[1, 2]$ 可以被区间 $[1, 3]$ 覆盖（注意，因为给定的区间中有两个区间是 $[1, 3]$，你只需要任选其中一个即可）；
2. 询问 $[1, 3]$ 可以被区间 $[1, 3]$ 覆盖；
3. 询问 $[1, 4]$ 不能被任何区间的并集覆盖；
4. 询问 $[1, 5]$ 不能被任何区间的并集覆盖。

数据规模与约定

• 对于 $30\%$ 的数据，$n,m \le 20, r_i, y_i \le 50$
• 对于 $60\%$ 的数据，$n,m \le 2000, r_i, y_i \le 5000$
• 对于 $100\%$ 的数据，$1 \le n,m \le 2 \cdot 10^5, 0 \le l_i \lt r_i \le 5 \cdot 10^5, 0 \le x_i \lt y_i \le 5 \cdot 10^5$