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 \operatorname{xor}(a_0, a_1, \dots, a_p) = x~, where ~\gcd~ is greatest common factor and ~\operatorname{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