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 ≤ 105) in array. The second line contains n integers – the elements ai (1 ≤ ai ≤ 109) of array. The third line gives the number of queries m (1 ≤ m ≤ 105). Each of the next 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