Given an array of integers a (len(a) < 10^5, 1 <= a[i] <= 10^9).

There are q queries of two types:

In the first type, two numbers x (0 <= x < len(a)) and y (1 <= y <= 10^9) are given. You need to change the element of the array a at position x to y.

In the second type, two numbers l and r are given (0 <= l < len(a), 0 <= r < len(a), l < r). You need to find two different indices x1 and x2 belonging to the segment from l to r (inclusive) such that their greatest common divisor (GCD) is the largest possible among all pairs (output the GCD).

I know how to solve this problem with brute force O(qn^2), but I am personally interested in finding a solution with a better complexity (O(qlog(N))).