给定一个长度为 $n$ 的升序数组 $A$，其中第 $i$ 个元素为 $A_i$，且 $A_1 = 1$。

利用该数组构建一个货币系统。对于任意正整数 $x$，定义货币张数函数为 $f(x, n)$，其中 $n$ 表示数组的长度。该函数表示在该货币系统下支付 $x$ 元所需的最少纸币张数，遵循贪心原则，即总是优先使用面值尽可能大的纸币。对于任意正整数 $x$ 和任意正整数 $y \in [1, n]$，$f(x, y)$ 满足：

$$ f(x, y) = \begin{cases} \lfloor \frac{x}{A_y} \rfloor + f(x \bmod A_y, y - 1) & y > 1 \\ x & y = 1 \end{cases} $$

你需要处理 $q$ 次查询。对于每次查询，给定一个整数 $m$，确定有多少个正整数 $x$ 满足 $f(x, n) = m$。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($1 \le n \le 10^5, 1 \le q \le 10^6$)，分别表示数组 $A$ 的长度和查询次数。

第二行包含 $n$ 个正整数 $A_1, A_2, \dots, A_n$ ($1 = A_1 < A_2 < \dots < A_n \le 10^6$)，即数组 $A$ 的元素。

第三行包含 $q$ 个整数 $m_1, m_2, \dots, m_q$ ($1 \le m_i \le 10^9$)，其中 $m_i$ 为第 $i$ 次查询的值。

输出格式

输出一行，包含 $q$ 个由空格分隔的整数。第 $i$ 个整数为第 $i$ 次查询的答案。

样例

样例输入 1

6 2
1 5 10 20 50 100
1 2

样例输出 1

6 18

说明

对于样例，货币系统中给出了六种面值的纸币：1元、5元、10元、20元、50元和100元。当支付6元时，必须使用两张纸币：一张1元纸币和一张5元纸币，即 $f(6, 6) = 2$。虽然理论上可以使用六张1元纸币来支付6元，但这种方法不满足优先使用大面值纸币的原则，因此不符合本题中该函数的定义。