問題文

長さが$N$の数列$A$が与えられます．この数列に対して$Q$個のクエリが与えられるので，順に処理してください．

クエリ

$i$番目（$1 \leq i \leq Q$）のクエリでは，$w_i, x_i, y_i, z_i$（$1 \leq w_i \leq x_i \leq N$ かつ $1 \leq y_i \leq z_i \leq N$）が与えられるので，$\displaystyle \prod_{w_i \leq k \leq x_i}A_k$ と $\displaystyle \prod_{y_i \leq k \leq z_i}A_k$ の最大公約数を$1000000007$で割った余りを出力する．

ただし，$\displaystyle \prod_{l \leq k \leq r}A_k$ とは $A_{l} \times A_{l + 1} \times A_{l + 2} \times \dots \times A_{r}$ のことである．

制約

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq A_i \leq 10^2 \quad (1 \leq i \leq N)$
• 各クエリにおいて $1 \leq w \leq x \leq N$ かつ $1 \leq y \leq z \leq N$
• 入力はすべて整数

入力

出力

各クエリにおいて，$\displaystyle \prod_{w \leq k \leq x}A_k$ と $\displaystyle \prod_{y \leq k \leq z}A_k$ の最大公約数を$1000000007$で割った余りを出力．

サンプル

10 5
39 49 9 22 28 5 23 40 26 14
1 3 7 10
3 7 4 6
5 8 3 5
8 8 3 3
2 2 2 2

91
3080
56
1
49

• クエリ$1$
  $39 \times 49 \times 9 = 17199$ と $23 \times 40 \times 26 \times 14 = 334880$ の最大公約数は $91$ です．
• クエリ$2$
  $9 \times 22 \times 28 \times 5 \times 23 = 637560$ と $22 \times 28 \times 5 = 3080$ の最大公約数は $3080$ です．
• クエリ$3$
  $28 \times 5 \times 23 \times 40 = 128800$ と $9 \times 22 \times 28 = 5544$ の最大公約数は $56$ です．
• クエリ$4$
  $40$ と $9$ の最大公約数は $1$ です．
• クエリ$5$
  $49$ と $49$ の最大公約数は $49$ です．