题目描述

给定一个长度为$N$的序列$A$，要求维护两种操作：

• 将一个区间里的数加上$x$
• 问一个区间里的所有数的最大公约数

输入格式

第一行一个正整数$N$，代表序列长度

第二行$N$个正整数，代表序列$A$

第三行一个正整数$M$，代表操作次数

接下来有$M$行，每行三个整数$op,L,R$

• 如果$op=0$，那么要求输出$[L,R]$之间的所有数的最大公约数
• 如果$op\ne 0$，那么将$[L,R]$里的所有数加上$op$

输出格式

对每个查询操作，输出一行一个正整数，代表区间里的最大公约数

说明&提示

数据范围

$1\le N,M\le 100000,1\le op,A_i\le 10^9$

有$30\%$数据点满足每次只修改一个数

样例1解释

• A=[6,3,38,49]
• Output gcd(6,3,38)=1
• A->[6,3,36,49]
• Output gcd(6,3,36)=3
• A->[6,12,36,49]
• Output gcd(6,12)=6
• A->[6,12,42,49]
• Output gcd(42,49)=7