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 positive integers
, Roger wants to write a program to support the following two types of operations:
1 i x
: change(
) to
(
).
2 x
: output the minimal index(
) such that
, where
is greatest common factor and
is bitwise XOR. If there is no such index
, output
.
Input Specification
The first line consists of an integer (
), the number of elements in the array.
The second line consists of positive integers
(
). Note that the array is 0-indexed.
The third line consists of an integer , (
), the number of operations.
The next lines consist of
operations as described above. For each type
operation,
and
. For each type
operation,
.
Output Specification
Output the minimal index for each type
operation. If there is no such index, output
.
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
Comments