Вітя потрапив у країну невивчених уроків. Для того, щоб повернутися додому йому потрібно виконати багато задач. У цій задачі він повинен виграти у стражів у НСД-грі. Правила цієї гри дуже прості: є масив натуральних чисел, після чого гравці вибирають два числа 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 у окремому рядку виведіть відповідь на запит.