У країні невивчених уроків
У країні невивчених уроків
Вітя потрапив у країну невивчених уроків. Для того, щоб повернутися додому йому потрібно виконати багато задач. У цій задачі він повинен виграти у стражів у НСД-грі. Правила цієї гри дуже прості: є масив натуральних чисел, після чого гравці вибирають два числа l та r, і їм потрібно порахувати найбільший спільний дільник (НСД) усіх елементів у масиві з індексами від l до r включно, хто швидше порахує, той і виграв. Щоб уникунти нечестних ігр, вони іноді міняють деякі числа в масиві на інші.
Вітя дуже хоче додому, допоможіть йому в цьому, для чого напишіть програму, яка буде дуже швидко рахувати НСД на заданому проміжку.
Вхідні дані
Перший рядок містить кількість елементів n (1 ≤ n ≤ 10^5
) у масиві. У другому рядку знаходиться n чисел – елементи масиву (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