D - Calculating GCD /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400

問題文

長さ 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 に変更されています。


入力

入力は以下の形式で標準入力から与えられる。

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

出力

i = 1, 2, \cdots, Q について X = S_i とした場合の答えを順に出力せよ。


入力例 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