# In the Country of Unlearned Lessons

# In the Country of Unlearned Lessons

Victor came to the country of unlearned lessons. In order to get back home he needs to perform many tasks. In this task he has to beat the guard in **GCD**-game. The rules of this game are very simple: There is an array of positive integers. The players choose two numbers **l** and **r**, and they need to find the greatest common divisor (**GCD**) of all elements in array with indexes from **l** to **r** inclusively. Who finds faster, that wins. To avoid unfair games, they sometimes replace some numbers in array to others.

Victor really wants to go home. Help him in it! Write a program that will quickly calculate the **GCD** on a given interval.

#### Input

The first line contains the number of elements **n** (**1** ≤ **n** ≤ `10`

) in array. The second line contains ^{5}**n** integers – the elements `a`

(_{i}**1** ≤ `a`

≤ _{i}`10`

) of array. The third line gives the number of queries ^{9}**m** (**1** ≤ **m** ≤ `10`

). Each of the next ^{5}**m** lines contains three integers **q**, **l**, **r** (**1** ≤ **l** ≤ **r** ≤ **n**). If **q** = **1**, find the **GCD** of elements on an interval [**l**, **r**], if **q** = **2**, change the element at position **l** to number **r**.

#### Output

For each query with number **1** print the answer on a separate line.

5 2 4 6 10 8 6 1 1 5 1 2 3 2 5 15 2 3 10 1 3 5 1 1 5

2 2 5 1