配点 : $500$ 点

問題文

$N$ 個の正整数からなる数列 $A$ が与えられます。 また、以下のようなクエリが $Q$ 個与えられます。

• 数列 $A$ は区間 $[L,R]$ において「pairwise coprime」ですか？

ただし、「$L \leq i < j \leq R$ となる全ての $(i,j)$ の組について、$\mathrm{gcd}(A_i, A_j)=1$」のとき、
かつそのときに限り、数列 $A$ は区間 $[L,R]$ において「pairwise coprime」であるといいます。
$\mathrm{gcd}$ は最大公約数を表します。

各クエリに答えてください。

制約

• $2 \leq N \leq 10^{5}$
• $2 \leq A_i \leq 10^{4}$ $(1 \leq i \leq N)$
• $1 \leq Q \leq 10^{4}$
• $1 \leq L_i < R_i \leq N$ $(1 \leq i \leq Q)$
• 入力は全て整数である。

入力

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

出力

各クエリについて、数列 $A$ は区間 $[L,R]$ において「pairwise coprime」であるならば「Yes」、そうでなければ「No」を出力してください。
$i$ 個目のクエリに対する答えを $i$ 行目に出力してください。

サンプル 1

10 5
2 4 8 8 7 15 6 9 4 11
1 5
4 6
4 7
8 10
2 3

No
Yes
No
Yes
No

$1$ つ目のクエリについて、例えば

• $\mathrm{gcd}(A_1, A_2)=\mathrm{gcd}(2, 4)=2$

となるため、区間 $[1,5]$ において「pairwise coprime」ではありません。

$2$ つ目のクエリについて、

• $\mathrm{gcd}(A_4, A_5)=\mathrm{gcd}(8, 7)=1$
• $\mathrm{gcd}(A_4, A_6)=\mathrm{gcd}(8, 15)=1$
• $\mathrm{gcd}(A_5, A_6)=\mathrm{gcd}(7, 15)=1$

となるため、区間 $[4,6]$ において「pairwise coprime」です。