Дан массив целых чисел a(len(a) < 10^5, 1 <= a[i] <= 10^9)

дано q запросов двух типов

В первом из них заданы два числа x(0 <= x < len(a)) и y(1 <= y <= 10^9) требуется изменить елемент массива а с позицией x на y

Во втором же заданы два числа: l,r(0 <= l < len(a), 0<= r < len(a), l < r) требуется найти два разных таких индекса x1,x2 принадлежащих отрезку от l до r включительно таких что их НОД будет максимально возмжным из всех пар(вывести его)

Я умею решать эту задачу полным перебором O(q*n^2) но мне лично интересно узнать есть ли решение за нормальную асимптотику(O(q*log(N))).