The Greatest Common Divisor (GCD) of two integers, \(a\) and \(b\), is the largest number which divides both \(a\) and \(b\). For example: \(GCD(10, 5) = 5\), \(GCD(21, 14) = 7\). Let us assume \(GCD(0, 0) = 0\).

You are given an array, \(A\), of \(N\) integers. You are tasked to answer \(Q\) queries. There are two types of queries:

1. print the GCD of the integers in \(A\) from index \(i\) to index \(j\) (\(i \leq j\)), i.e. \(GCD(A[i..j])\), where \(i\) and \(j\) are inclusive.
2. update any element within the array to a specified value

Input specification

The first line of input contains the integer \(N\) (\(1 \leq N \leq 10^5\)). Following this line is \(N\) space separated integers (\(-2*10^9 \leq a_i \leq 2*10^9\) where \(a_i\) denotes the \(i^{\text{th}}\) integer).

The next line contains a single integer \(Q\) (\(1 \leq Q \leq 10^5\)) describing the number of queries to answer. Then \(Q\) lines follow, each of these lines are may be of the form:

• 1 i j
  • Print the Greatest Common Divisor of the integers in \(A\) from index \(i\) to index \(j\)
  • Constraints: \(i \leq j\) and \(0 \leq i, j < N\)
• 2 i x
  • Update \(A[i]\) to the value \(x\), i.e. set \(A[i] = x\)
  • Constraints: \(-2*10^9 \leq x \leq 2*10^9\) and \(0 \leq i < N\)

Output specification

For each query which begins with \(1\), please print the Greatest Common Divisor of the integers in A from index \(i\) to index \(j\).

Example input

5
21 21 21 21 21
4
1 0 4
2 0 14
2 2 7
1 0 2

Example output

21
7

Notes

This problem has a lot of input and output. Please use fast input and output methods. Some tips are given here.