eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

В стране невыученных уроков

В стране невыученных уроков

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
prb4481

Витя попал в страну невыученных уроков. Для того, чтобы вернуться домой ему нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа l и r, и им надо посчитать наибольший общий делитель (НОД) всех элементов в массиве с индексами от l до r включительно. Кто быстрее посчитает, тот и выиграл. Чтобы избежать нечестных игр, они иногда заменяют некоторые числа в массиве на другие.

Витя очень хочет домой, помогите ему в этом, для чего напишите программу, которая будет очень быстро считать НОД на заданном промежутке.

Входные данные

Первая строка содержит количество элементов n (1n10^5) в массиве. Во второй строке находится n чисел – элементы a[i] (1a[i]10^9) массива. В третьей строке находится количество запросов m (1m10^5). Далее в m строках находятся по три числа q, l, r (1lrn). Если q = 1, требуется посчитать НОД элементов на промежутке [l, r], если q = 2, то надо заменить элемент в позиции l на число r.

Выходные данные

Для каждого запроса с номером 1 в отдельной строке выведите ответ на запрос.

Пример

Входные данные #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
Выходные данные #1
2
2
5
1
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года