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

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

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

Вхідні дані

Перший рядок містить кількість елементів $n(1\le n\le 10^5)$ у масиві. У другому рядку знаходиться $n$ чисел $a_i(1\le a_i\le 10^9)$ — елементи масиву. У третьому рядку знаходиться кількість запитів $m(1\le m\le 10^5)$. Далі у $m$ рядках знаходиться по три числа $q,l,r(1\le l\le r\le n)$.

• Якщо $q=1$, то потрібно порахувати НОД елементів на проміжку $[l,r]$;

• Якщо $q=2$, то потрібно замінити елемент у позиції $l$ на число $r$.

Вихідні дані

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

Приклади