AT_judge_update_202004_d Calculating GCD

[problemUrl]: https://atcoder.jp/contests/judge-update-202004/tasks/judge_update_202004_d 長さ $ 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 $ の値を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \leq\ N,\ Q\ \leq\ 10^5 $ - $ 1\ \leq\ A_i\ \leq\ 10^9 $ - $ 1\