1905 - GCD

問題

数列$A$が与えられる。以下のクエリを処理せよ。

クエリ１

1 $x$ $k$

$A$の$x$番目の値を$k$に変更する。

クエリ２

2 $l$ $r$

($A_l$,$A_{l+1}$,...$A_r$)の最大公約数を出力せよ。

入力

$N$
$A_1$ $A_2$ ... $A_N$
$Q$
$Query1$
$Query2$
 :
$QueryQ$

出力

クエリ2の結果を改行区切りで出力せよ。

制約

$1 \leq N,Q \leq 10^6$

$1 \leq A_i \leq 10^9(1 \leq i \leq N)$

$1 \leq k \leq 10^9$

$1 \leq l < r \leq N$

$1 \leq x \leq N$

クエリ2は必ず存在する

入力はすべて整数

入出力

入力例１

10
3 1 4 1 5 9 2 6 5 3
5
2 1 4 
2 1 10
1 2 4
1 4 4
2 2 4

出力例１

1
1
4

1,2つめのクエリはそれぞれ
$gcd(3,1,4,1) = 1$
$gcd(3,1,4,1,5,9,2,6,5,3) = 1$
となります。
3,4つめのクエリ後は$A$は$(3,4,4,4,5,9,2,6,5,3)$となります。
5つめのクエリは$gcd(4,4,4) = 4$となります。

入力例２

6
1 2 6 5 6 9 
3
1 1 9
1 3 6
2 5 6    

出力例２

3

出力するものがない場合でも最後に改行を入れてください。