В стране невыученных уроков
В стране невыученных уроков
Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа l и r, и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от l до r включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.
Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.
Входные данные
Первая строка содержит количество элементов n (1 ≤ n ≤ 10^5) в массиве. Во второй строке находится n чисел – элементы a[i] (1 ≤ a[i] ≤ 10^9) массива. В третьей строке находится количество запросов m (1 ≤ m ≤ 10^5). Далее в m строках находятся по три числа q, l, r (1 ≤ l ≤ r ≤ n). Если q = 1, требуется посчитать НОД элементов на промежутке [l, r], если q = 2, то надо заменить элемент в позиции l на число r.
Выходные данные
Для каждого запроса с номером 1 в отдельной строке выведите ответ на запрос.
Пример
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