给定 $$$n$$$ 间隔,格式为 $$$[l; r]$$$ 在数轴上。
您还会收到 $$$m$$$ 形式的查询 $$$[x; y]$$$。您必须采取的最小间隔数是多少,以便从 $$$x$$$ 到 $$$y$$$ 的每个点(不一定是整数)至少被其中一个点覆盖?
如果您无法选择间隔来覆盖从 $$$x$$$ 到 $$$y$$$ 的每个点,则为该查询打印 -1。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$) — 分别是间隔数和查询数。
接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i < r_i \le 5 \cdot 10^5$$$) — 给定的间隔。
接下来的 $$$m$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$0 \le x_i < y_i \le 5 \cdot 10^5$$$) — 查询。
输出
打印 $$$m$$$ 整数。第 $$$i$$$ 个数字应该是第 $$$i$$$ 查询的答案:要么是您必须采用的最小间隔数,以便从 $$$x_i$$$ 到 $$$y_i$$$ 的每个点(不一定是整数)至少被其中之一覆盖,要么是 -1(如果您无法选择间隔)以便覆盖从 $$$x_i$$$ 到 $$$y_i$$$ 的每个点。
示例
输入 #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; 3]$$$可以被区间$$$[1覆盖; 3]$$$;
2.查询$$$[1; 4]$$$ 可以被区间 $$$[1; 覆盖; 3]$$$ 和 $$$[2; 4]$$$。没有办法覆盖$$$[1; 4]$$$ 单个间隔;
3.查询$$$[3; 4]$$$可以被区间$$$[2覆盖; 4]$$$。除了给定的查询之外,涵盖其他点并不重要。
在第二个示例中,有四个查询:
1.查询$$$[1; 2]$$$可以被区间$$$[1覆盖; 3]$$$。请注意,您可以选择两个给定间隔中的任何一个 $$$[1; 3]$$$;
2.查询$$$[1; 3]$$$可以被区间$$$[1覆盖; 3]$$$;
3.查询$$$[1; 4]$$$不能被任何一组区间覆盖;
4.查询$$$[1; 5]$$$ 不能被任何一组区间覆盖。请注意间隔 $$$[1; 3]$$$ 和 $$$[4; 5]$$$ 一起不包括 $$$[1; 5]$$$ 因为即使是非整数点也应该被覆盖。例如,这里的 $$$3.5$$$ 不包括在内。