В стране невыученных уроков

Витя попал в страну невыученных уроков. Для того чтобы вернуться ему домой, нужно выполнить множество заданий. В этой задаче он должен выиграть у стражей в НОД-игру. Правила этой игры очень простые: есть массив натуральных чисел, после чего игроки выбирают два числа $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$ в отдельной строке выведите ответ на запрос.

Примеры