When GCD meets XOR

View as PDF

Points: 17
Time limit: 0.6s
Memory limit: 512M

Problem type

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