e-olymp
favorite Нам необхідно трохи Вашої допомоги щоб сайт продовжував працювати, натисніть на банер щоб дізнатись більше.
Змагання

ADA University - January 13 - Segment Tree

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

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

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

Вхідні дані

Перший рядок містить кількість елементів n (1n105) у масиві. У другому рядку знаходиться n чисел – елементи масиву (1ai109). У третьому рядку знаходиться кількість запитів m (1m105). Далі у m рядках знаходиться по три числа q, l, r (1lrn). Якщо q = 1, потрібно порахувати НОД елементів на проміжку [l, r], якщо q = 2, то потрібно замінити елемент у позиції l на число r.

Вихідні дані

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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 року