问题文

高桥君喜欢创建数列并对其进行各种操作。特别是，他喜欢对区间进行各种操作，如计算区间和、区间最大公约数等。

因此，高桥决定对某个数列进行操作，统计使得区间最大公约数为给定值 $x$ 的区间的数量。高桥使用程序来解决这个问题，但他意识到随着数列变长，程序的运行时间会非常长。

你的任务是为高桥编写一个程序，即使数列很长也能快速运行。另外，为了提供额外功能，对于相同的数列，即使存在多个 $x$ 的候选，也要提供查询功能，以便计算所有 $x$ 的结果。

给定一个长度为 $n$ 的数列 $A=\\{a_1,a_2,..,a_n\\}$，以及查询数目 $m$ 和 $x_1,x_2,..,x_m$。请输出每个 $x_i (1 ≦ i ≦ m)$ 对应的区间中所有包含的数的最大公约数为 $x_i$ 的区间 \[s,t\] (1 ≦ s ≦ t ≦ n) 的数量。

例如，当 $A=\\{1,2,4\\}$ 时，最大公约数为 1 的区间有 3 个，分别是 \[1,1\],\[1,2\],\[1,3\]；最大公约数为 2 的区间有 2 个，分别是 \[2,2\],\[2,3\]；最大公约数为 4 的区间只有 1 个，即 \[3,3\]。

输入

输入按以下格式从标准输入中给出。

$n　m$ $a_1$ $a_2$ : $a_n$ $x_1$ $x_2$ : $x_m$

• 第 1 行为两个整数 $n (1 ≦ n ≦ 100,000)$ 和查询数目 $m (1 ≦ m ≦ 100,000)$，以空格分隔。
• 第 2 行到第 $n$ 行给出数列 $A$ 的值。其中第 $i$ 行给出数列 $A$ 的第 $i$ 个值，表示为整数 $a_i (1 ≦ a_i ≦ 10^9)$。
• 第 $n+2$ 行到第 $n+m+1$ 行给出要查询的值。其中第 $i$ 行给出第 $i$ 个查询中 $x$ 的值，表示为整数 $x_i (1 ≦ x_i ≦ 10^9)$。

输出

按顺序输出每个查询的答案，共 $m$ 行。输出末尾添加换行符。

输入例1

3 4
1
2
4
1
2
3
4

输出例1

3
2
0
1

给定的数列与问题描述中的相同。

输入例2

6 7
12
6
4
3
2
1
1
2
3
4
6
12
8

输出例2

13
3
1
1
2
1
0

输入例3

5 8
4
6
42
28
41
1
2
4
6
7
14
14
41

输出例3

4
4
1
2
0
1
1
1