题目描述

小Z学习了“皮筋穿越”的魔术手法！他可以瞬间把两个互相交错的皮筋分开！

现在桌上有 $n$ 个皮筋，每个皮筋的左右端点位置坐标为 $[l_i,r_i]$。所有端点都两两不同，且初始时没有任何一个皮筋包含另一个皮筋。

有 $q$ 次独立的询问：

• 每次给定正整数 $k$，即小Z的手法娴熟度，他可以每次选择当前满足以下条件的两个交错皮筋$[a,c]$ 与 $[b,d]$：

  $$a<b<c<d,\;c-b<k$$

• 然后小Z可以完成魔术，即将两个皮筋分开，变为 $[a,b]$ 与 $[c,d]$

不要求操作后的区间仍满足最初的包含限制。对于每个询问，求出小Z最多能进行多少次魔术操作。

输入格式

第一行两个整数 $n,q$。

接下来 $n$ 行，每行两个整数 $l_i,r_i$。

接下来 $q$ 行，每行一个整数 $k$。

输出格式

对于每个询问，输出一行一个整数，表示答案。

输入输出样例

4 5
1 10
4 13
8 16
12 20
1
2
3
4
5

0
1
3
4
5

样例 $\tt \#1$说明

当 $k=3$ 时，可以依次进行

最多可以进行三次操作。

10 10
16 66
35 91
13 58
32 89
8 57
30 76
3 56
1 48
25 71
24 68
1
833
1000000000000000000
1
1
14
516
14
3
2

0
45
45
0
0
45
45
45
0
0

数据范围

$15\%:n,q\le 10$

$30\%:n,q\le 2000$

另外 $10\%:q=1$

另外 $10\%:$ 所有初始区间有公共交集

$100\%:1\le n,q\le 2\times10^5$, $1\le l_i<r_i\le10^{18}, 1\le K\le10^{18}$

保证所有端点两两不同，且初始时没有区间严格包含另一个区间。