题目背景

fw神犇最喜欢的数论题就是gcd，也就是最大公因数。他一般都是这么写一个gcd的代码的（与事实不符不要怪出题人，下同）。

int gcd(int x,int y)
{
    return y==0?x:gcd(y,x%y);
}

后来，他又完成了一个求某区间内所有数gcd的值，他是这么写的：

int l,r,ans;scanf("%d%d",&l,&r);
ans=a[l];
for(int i=l+1;i<=r;i++)
    ans=gcd(ans,a[i]);
printf("%d\n",ans);   

题目描述

后来，他发现gcd还有一种玩法。
他原先有长度为\(n\)一个数列\(a\)，分别是\(a_1,a_2...a_n\),他还有两个按钮。
* 第一个按钮后面有2个输入框，表示\(i\)和\(x\)的值。它表示可以把数列中第\(i\)项（即\(a_i\)）修改为\(x\)；
* 第二个按钮之后也有2个输入框，表示l和r的值。他表示fw神犇的机器要计算区间\([l,r]\)的最大公因数（如果不知道什么是区间的话，可以理解为\(l\)到\(r\)的范围内，包括\(l\)和\(r\)）。
可是关键的时候，fw神犇的机器坏了……于是他找来了你，让你帮忙解决问题。

我们将会给出fw神犇想进行的操作，请你对于所有“按钮2”的操作，输出一个答案表示区间内的最大公因数。

输入输出格式

输入格式：

输入第一行为一个数，表示操作总数\(n\)。
第二行有\(n\)个数，表示每个数的初值。
接下来一行是\(q\)，表示操作个数。
紧接着有\(q\)行，每行包含\(3\)个数\(opt,a,b\)。
如果\(opt=1\)，那么表示fw神犇进行了一次按钮1的操作（如题面），后面就表示\(i\)和\(x\)。
如果\(opt=2\)，那么表示fw神犇进行了一次按钮2的操作（如题面），后面就表示\(l\)和\(r\)。

输出格式：

对于每一个\(opt=2\)的操作，输出一个值，表示区间内的最大公因数。

输入输出样例

输入样例#1:

5
2 4 6 12 54
3
2 2 4
1 3 8
2 2 4

输出样例#1：

2
4

输入样例#2：

1
1
1
2 1 1

输出样例#2

1

说明

数据范围
* 对于\(40\)%的数据，满足\(n \le 2000 , q \le 2000\)；
* 对于\(70\)%的数据，满足\(n \le 2000 , q \le 30000\)；
* 对于\(100\)%的数据，满足\(n \le 300000 , q \le 300000\)。