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

У країні невивчених уроків

У країні невивчених уроків

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
prb4481

Вітя потрапив у країну невивчених уроків. Для того, щоб повернутися додому йому потрібно виконати багато задач. У цій задачі він повинен виграти у стражів у НСД-грі. Правила цієї гри дуже прості: є масив натуральних чисел, після чого гравці вибирають два числа l та r, і їм потрібно порахувати найбільший спільний дільник (НСД) усіх елементів у масиві з індексами від l до r включно, хто швидше порахує, той і виграв. Щоб уникунти нечестних ігр, вони іноді міняють деякі числа в масиві на інші.

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

Вхідні дані

Перший рядок містить кількість елементів n (1n10^5) у масиві. У другому рядку знаходиться n чисел – елементи масиву (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 року