Problem Description

Takahashi loves creating sequences and performing various operations on them. Especially, he loves operations related to intervals, such as calculating the sum or the greatest common divisor (GCD) of an interval.

Therefore, Takahashi decided to count the number of intervals in a certain sequence where the GCD of all numbers in the interval equals a certain value $x$. Takahashi solved this problem using a program, but he noticed that the longer the sequence, the more time it takes.

Your task is to write a program for Takahashi that works fast even for long sequences. Additionally, as a bonus feature, you decided to include a query function that can handle multiple candidates for $x$ for the same sequence.

You are given a sequence of length $n$, $A=\{a_1,a_2,..,a_n\}$, and the number of queries $m$, along with $x_1,x_2,..,x_m$. For each $x_i\ (1\ ≦\ i\ ≦\ m)$, output the number of intervals $[s,t]\ (1\ ≦\ s\ ≦\ t\ ≦\ n)$ where the GCD of all numbers in the interval equals $x_i$.

For example, for $A=\{1,2,4\}$, the intervals with GCD 1 are $[1,1],[1,2],[1,3]$, which are 3 in total. The intervals with GCD 2 are $[2,2],[2,3]$, which are 2 in total. The interval with GCD 4 is $[3,3]$, which is 1 in total.

Input Format

The input is given from the standard input in the following format:

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

• The first line contains two integers, $n\ (1\ ≦\ n\ ≦\ 100,000)$ representing the length of the sequence, and $m\ (1\ ≦\ m\ ≦\ 100,000)$ representing the number of queries, separated by a space.
• The next $ n $ lines contain the values of the sequence $ A $. The $ i $th line contains an integer $a_i\ (1\ ≦\ a_i\ ≦\ 10^9)$ representing the $ i $th value of the sequence $ A $.
• The next $ m $ lines contain the values to be queried. The $ i $th line contains an integer $x_i\ (1\ ≦\ x_i\ ≦\ 10^9)$ representing the value of $ x $ for the $ i $th query.

Output Format

Output the answers to each query in order, from the first line to the $ m $th line. Ensure a newline at the end of the output.

Sample Input and Output

Sample Input #1

3 4
1
2
4
1
2
3
4

Sample Output #1

3
2
0
1

Sample Input #2

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

Sample Output #2

13
3
1
1
2
1
0

Sample Input #3

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

Sample Output #3

4
4
1
2
0
1
1
1

Notes/Hints

Sample Explanation 1

The given sequence is the one mentioned in the problem statement.

见题面 Input 部分

见题面 Output 部分