Range GCD

You are given a sequence of $N$ natural numbers $A_1, A_2, \dots, A_N$. Two kinds of operations act on this sequence.

• Add the same value to every element of a contiguous range.
• Compute the greatest common divisor of the elements in a contiguous range.

Process the operations in the order they are given, and print an answer for every operation of the second kind.

The first line contains the number of elements $N$. ($1 \le N \le 100000$)

The second line contains the $N$ elements of the sequence, separated by spaces. The $i$-th number is $A_i$, and $1 \le A_i \le 10^9$.

The third line contains the number of operations $Q$. ($1 \le Q \le 100000$)

Each of the next $Q$ lines contains one operation as three integers $T$, $A$, $B$.

• If $T$ is not 0, add $T$ to every element from the $A$-th through the $B$-th.
• If $T$ is 0, print the greatest common divisor of the elements from the $A$-th through the $B$-th.

$T$ satisfies $0 \le T \le 10^9$, and $A$ and $B$ satisfy $1 \le A \le B \le N$. At least one operation has $T$ equal to 0.

For every operation with $T$ equal to 0, print the greatest common divisor of the requested range on its own line, in the order the operations are given.