問題文

長さがNNの数列AAが与えられます.この数列に対してQQ個のクエリが与えられるので,順に処理してください.

クエリ

ii番目(1iQ1 \leq i \leq Q)のクエリでは,wi,xi,yi,ziw_i, x_i, y_i, z_i1wixiN1 \leq w_i \leq x_i \leq N かつ 1yiziN1 \leq y_i \leq z_i \leq N)が与えられるので,wikxiAk\displaystyle \prod_{w_i \leq k \leq x_i}A_kyikziAk\displaystyle \prod_{y_i \leq k \leq z_i}A_k の最大公約数を10000000071000000007で割った余りを出力する.

ただし,lkrAk\displaystyle \prod_{l \leq k \leq r}A_k とは Al×Al+1×Al+2××ArA_{l} \times A_{l + 1} \times A_{l + 2} \times \dots \times A_{r} のことである.

制約

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

入力

N QN\ Q
A1ANA_1 \dots A_N
w1 x1 y1 z1w_1 \ x_1 \ y_1 \ z_1
w2 x2 y2 z2w_2 \ x_2 \ y_2 \ z_2
\vdots
wQ xQ yQ zQw_Q \ x_Q \ y_Q \ z_Q

出力

各クエリにおいて,wkxAk\displaystyle \prod_{w \leq k \leq x}A_kykzAk\displaystyle \prod_{y \leq k \leq z}A_k の最大公約数を10000000071000000007で割った余りを出力.

サンプル

入力例1
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
出力例1
91
3080
56
1
49
  • クエリ11
    39×49×9=1719939 \times 49 \times 9 = 1719923×40×26×14=33488023 \times 40 \times 26 \times 14 = 334880 の最大公約数は 9191 です.
  • クエリ22
    9×22×28×5×23=6375609 \times 22 \times 28 \times 5 \times 23 = 63756022×28×5=308022 \times 28 \times 5 = 3080 の最大公約数は 30803080 です.
  • クエリ33
    28×5×23×40=12880028 \times 5 \times 23 \times 40 = 1288009×22×28=55449 \times 22 \times 28 = 5544 の最大公約数は 5656 です.
  • クエリ44
    404099 の最大公約数は 11 です.
  • クエリ55
    49494949 の最大公約数は 4949 です.

提出


Go (1.21)