When GCD meets XOR

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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, \ldots, 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, \ldots, a_p) \times XOR(a_0, a_1, \ldots, a_p) = x, where GCD is greatest common factor and 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

1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
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



There are no comments at the moment.