구간 최대공약수

자연수 $N$개로 이루어진 수열 $A_1, A_2, \dots, A_N$이 있다. 이 수열에 다음 두 가지 연산을 수행한다.

• 연속한 구간의 모든 원소에 같은 값을 더한다.
• 연속한 구간에 있는 원소의 최대공약수를 구한다.

연산을 입력에 주어진 순서대로 처리하고, 최대공약수를 구하는 연산마다 답을 출력하라.

첫째 줄에 수열의 원소 개수 $N$이 주어진다. ($1 \le N \le 100000$)

둘째 줄에 수열의 원소 $N$개가 공백으로 구분되어 주어진다. $i$번째 수가 $A_i$이고, $1 \le A_i \le 10^9$이다.

셋째 줄에 연산의 개수 $Q$가 주어진다. ($1 \le Q \le 100000$)

이어지는 $Q$개의 줄에 연산이 한 줄에 하나씩 주어진다. 각 줄은 세 정수 $T$, $A$, $B$로 이루어진다.

• $T$가 0이 아니면 $A$번째 원소부터 $B$번째 원소까지 모든 원소에 $T$를 더한다.
• $T$가 0이면 $A$번째 원소부터 $B$번째 원소까지의 최대공약수를 출력해야 한다.

$T$는 $0 \le T \le 10^9$이고, $A$와 $B$는 $1 \le A \le B \le N$을 만족한다. $T$가 0인 연산은 하나 이상 주어진다.

$T$가 0인 연산마다 그 구간의 최대공약수를 입력에 주어진 순서대로 한 줄에 하나씩 출력한다.