In the Country of Unlearned Lessons

Victor found himself in a land of unlearned lessons. To return home, he must complete various tasks. One such task involves defeating a guard in a GCD game. The rules are straightforward: given an array of positive integers, the players select two numbers $l$ and $r$, and find the greatest common divisor (GCD) of all the elements in the array from index $l$ to $r$ inclusive. The player who finds the GCD the fastest wins. To prevent unfair play, some numbers in the array may be replaced occasionally.

Victor is eager to return home. Help him by writing a program that can quickly calculate the GCD over a specified interval.

Input

The first line contains the number of elements $n(1\le n\le 10^5)$ in array. The second line contains $n$ integers — the elements $a_i(1\le a_i\le 10^9)$ of array. The third line gives the number of queries $m(1\le m\le 10^5)$. Each of the next $m$ lines contains three integers $q,l,r(1\le l\le r\le n)$.

• If $q=1$, find the GCD of elements on an interval $[l,r]$;

• If $q=2$, change the element at position $l$ to number $r$.

Output

For each query with number $1$ print the answer on a separate line.

Examples