After learning prefix sum array and prefix max array, Roger wanted to try some more complicated prefix arrays, such as prefix GCD and XOR. More specifically, given an array of $n$ positive integers $a_0,a_1,\dots ,a_{n-1}$, Roger wants to write a program to support the following two types of operations:

• 1 i x: change $a_i$ ($0\le i\le n-1$) to $x$ ($1\le x\le {10}^9$).
• 2 x: output the minimal index $p$ ($0\le p\le n-1$) such that $gcd(a_0,a_1,\dots ,a_p)\times \mathrm{xor}(a_0,a_1,\dots ,a_p)=x$, where $gcd$ is greatest common factor and $\mathrm{xor}$ is bitwise XOR. If there is no such index $p$, output $-1$.

Input Specification

The first line consists of an integer $n$ ($1\le n\le {10}^5$), the number of elements in the array.

The second line consists of $n$ positive integers $a_i$ ($1\le a_i\le {10}^9$). Note that the array is 0-indexed.

The third line consists of an integer $q$, ($1\le q\le {10}^4$), the number of operations.

The next $q$ lines consist of $q$ operations as described above. For each type $1$ operation, $0\le i\le n-1$ and $1\le x\le {10}^9$. For each type $2$ operation, $0\le x\le {10}^{18}$.

Output Specification

Output the minimal index $p$ for each type $2$ operation. If there is no such index, output $-1$.

Sample Input

10
1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
10
1 7 20321280
2 162343680
2 1832232960000
1 0 92160
2 1234567
2 3989856000
2 833018560
1 3 8600
1 5 5306112
2 148900352

Sample Output

6
0
-1
2
8
8