Problem Description

You are given an integer sequence of length $ N $, $A_1, A_2, \cdots, A_N$.

You are also given $ Q $ integers greater than $ 1 $, $S_1, S_2, \cdots, S_Q$. For each $i = 1, 2, \cdots, Q$, find the answer for the following problem with $ X = S_i $.

• Initially, there is an integer $ X $. For each $j = 1, 2, \cdots, N$ in order, perform the operation of replacing $ X $ with $\gcd(X, A_j)$. If there exists a $ j $ such that $ X = 1 $ immediately after the $ j $-th operation, output the minimum such $ j $. If no such $ j $ exists, output the final value of $ X $.

Input Format

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

$ N $ $ Q $ $ A_1 $ $ A_2 $ $\cdots$ $ A_N $ $ S_1 $ $ S_2 $ $\cdots$ $ S_Q $

Output Format

For each $i = 1, 2, \cdots, Q$, output the answer for the case $ X = S_i $ in order.

Sample Input and Output

Sample Input #1

4 3
6 12 6 9
4 6 3

Sample Output #1

4
3
3

Sample Input #2

4 3
4 6 2 1
3 2 1000000000

Sample Output #2

1
4
4

Notes/Hints

Constraints

• $1 \leq N, Q \leq 10^5$
• $1 \leq A_i \leq 10^9$
• $1 < S_i \leq 10^9$
• All inputs are integers.

Notes

The greatest common divisor (GCD) of two integers $ X $ and $ Y $ greater than $ 0 $ is denoted by $\gcd(X, Y)$.

In C++, std::gcd can be used.

In Python, it has changed from fractions.gcd to math.gcd.

Sample Explanation 1

• For $ i = 1 $, $ X $ is initially $ 4 $. After 4 operations, $ X $ becomes $ 2, 2, 2, 1 $ respectively, and $ X = 1 $ for the first time after the 4th operation, so output $ 4 $.
• For $ i = 2 $, $ X $ is initially $ 6 $. After 4 operations, $ X $ becomes $ 6, 6, 6, 3 $ respectively, and $X \neq 1$ after the 4th operation, so output the final value of $ X $, which is $ 3 $.
• For $ i = 3 $, $ X $ is initially $ 3 $. After 4 operations, $ X $ becomes $ 3, 3, 3, 3 $ respectively, and $X \neq 1$ after the 4th operation, so output the final value of $ X $, which is $ 3 $.

见题面 Input 部分

见题面 Output 部分