区间树是我们熟悉的数据结构线段树的一个拓展，她的每个点仍然表示一个区间，但是区间的分割点不一定是中点。

For example, the following picture describe an interval tree on $[1,6]$:

类似线段树，我们能在区间树上做一些询问，我们定义询问 $[l,r]$ 的时间复杂度为我们定位区间 $[l,r]$ 所需要访问的点数。

更加正式的，我们定义 $S[l,r]$ 为定位区间 $[l,r]$ 需要访问的节点集合，一个节点 $v\in S[l,r]$ 需要满足以下条件。

1. v 代表的区间是 $[l,r]$ 的子区间，但是 $v$ 父节点不满足这个条件

2. v 中后代至少有一个节点满足条件 $1$

现在给定一个 $[1, n]$ 的区间树和 $q$ 次询问，每次询问包含一个正整数 $k$, 你需要求出有多少区间的时间复杂度恰好等于 $k$

Input

输入包含多组测试数据，每组数据的第一行两个整数 $n$ 和 $q$

每组数据的第二行包含 $n-1$ 个整数，以先序遍历的形式给出了树上每个非叶子节点的分割点，若 $[l,r]$ 的分割点为 $m$, 则其左孩子为 $[l,m]$, 右孩子为 $[m+1,r]$。

Output

对于每组询问，输出一行表示答案。

Sample 1

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

1
2
2
3
6
4
3

输入保证 $l\le m< r$, $n, q\le 10^5$ 以及 $k\le 10^9$, 所有数据的 $\sum n$ 和 $\sum q$ 均不超过 $5 \times 10^5$ 。

特别鸣谢楼天城和吉如一提供试题，数据。

时间限制：$5\texttt{s}$

空间限制：$256\texttt{MB}$

下载

样例数据下载