問題文

長さ N の整数列 A_1, A_2, \cdots, A_N があります。

Q 個の 1 より大きい整数 S_1, S_2, \cdots, S_Q が与えられるので、i = 1, 2, \cdots, Q について次の問題で X = S_i とした場合の答えを求めてください。

• 初め整数 X がある。j = 1, 2, \cdots, N の順に、X を \gcd(X, A_j) で置き換えるという操作を行う。j 回目の操作の直後に X = 1 であるような j が存在する場合はそのような j の最小値を、存在しない場合は最終的な X の値を求めよ。

制約

• 1 \leq N, Q \leq 10^5
• 1 \leq A_i \leq 10^9
• 1 < S_i \leq 10^9
• 入力は全て整数である

注記

2 つの 0 より大きい整数 X, Y の最大公約数を \gcd(X, Y) で表します。

C++ では std::gcd が利用できます。

Python では fractions.gcd から math.gcd に変更されています。

入力例 1

4 3
6 12 6 9
4 6 3

出力例 1

4
3
3

• i = 1 のとき、X は初め 4 です。4 回の操作の後、それぞれ X = 2, 2, 2, 1 となり、4 回の操作の後初めて X = 1 となるので 4 を出力してください。

• i = 2 のとき、X は初め 6 です。4 回の操作の後、それぞれ X = 6, 6, 6, 3 となり、4 回の操作の後も X \neq 1 であるので、最終的な X の値である 3 を出力してください。

• i = 3 のとき、X は初め 3 です。4 回の操作の後、それぞれ X = 3, 3, 3, 3 となり、4 回の操作の後も X \neq 1 であるので、最終的な X の値である 3 を出力してください。

入力例 2

4 3
4 6 2 1
3 2 1000000000

出力例 2

1
4
4