## GCD Queries

Points: 1
Time limit: 2.0s
Memory limit: 512M

Authors:
Problem type

The Greatest Common Divisor (GCD) of two integers, $$a$$ and $$b$$, is the largest number which divides both $$a$$ and $$b$$. For example: $$GCD(10, 5) = 5$$, $$GCD(21, 14) = 7$$. Let us assume $$GCD(0, 0) = 0$$.

You are given an array, $$A$$, of $$N$$ integers. You are tasked to answer $$Q$$ queries. There are two types of queries:

1. print the GCD of the integers in $$A$$ from index $$i$$ to index $$j$$ ($$i \leq j$$), i.e. $$GCD(A[i..j])$$, where $$i$$ and $$j$$ are inclusive.
2. update any element within the array to a specified value

#### Input specification

The first line of input contains the integer $$N$$ ($$1 \leq N \leq 10^5$$). Following this line is $$N$$ space separated integers ($$-2*10^9 \leq a_i \leq 2*10^9$$ where $$a_i$$ denotes the $$i^{\text{th}}$$ integer).

The next line contains a single integer $$Q$$ ($$1 \leq Q \leq 10^5$$) describing the number of queries to answer. Then $$Q$$ lines follow, each of these lines are may be of the form:

• 1 i j
• Print the Greatest Common Divisor of the integers in $$A$$ from index $$i$$ to index $$j$$
• Constraints: $$i \leq j$$ and $$0 \leq i, j < N$$
• 2 i x
• Update $$A[i]$$ to the value $$x$$, i.e. set $$A[i] = x$$
• Constraints: $$-2*10^9 \leq x \leq 2*10^9$$ and $$0 \leq i < N$$

#### Output specification

For each query which begins with $$1$$, please print the Greatest Common Divisor of the integers in A from index $$i$$ to index $$j$$.

#### Example input

5
21 21 21 21 21
4
1 0 4
2 0 14
2 2 7
1 0 2

#### Example output

21
7

#### Notes

This problem has a lot of input and output. Please use fast input and output methods. Some tips are given here.