НОД на отрезке

Дан массив натуральных чисел. Запросы: наибольший общий делитель всех чисел на отрезке и присвоение элементу нового значения.

Проверьте функцию на пригодность: $\gcd$ ассоциативен, $\gcd(\gcd(a,b),c) = \gcd(a,\gcd(b,c))$ — значит в дерево ложится. Нейтральный элемент — ноль: $\gcd(0, x) = x$.

Ноль в роли нейтрального смущает, но он правильный: ноль делится на всё, и наибольший общий делитель нуля и $x$ равен $x$.

В первой строке $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$ строк: g l r — НОД на отрезке, u i x — присвоить $a_i = x$ ($1 \le x \le 10^9$).

Для каждого запроса g выведите НОД на отдельной строке.