In the Country of Unlearned Lessons

In the Country of Unlearned Lessons

prb4481 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.


The first line contains the number of elements n (1n105) in array. The second line contains n integers – the elements ai (1ai109) of array. The third line gives the number of queries m (1m105). Each of the next m lines contains three integers q, l, r (1lrn). 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.


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

Time limit 1 second
Memory limit 128 MiB
Input example #1
2 4 6 10 8
1 1 5
1 2 3
2 5 15
2 3 10
1 3 5
1 1 5
Output example #1
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013