Dynamic GCD and XOR Prefix Query

Design a data structure that supports operations on a sequence of positive integers. Given a sequence (a_0, a_1, \ldots, a_{n-1}), you need to support the following two operations:

1. (\texttt{MODIFY}\ id\ x): Modify (a_{id}) to (x).
2. (\texttt{QUERY}\ x): Find the smallest integer (p) (where (0 \le p < n)) such that
[ \gcd(a_0, a_1, \ldots, a_p) \times \operatorname{xor}(a_0, a_1, \ldots, a_p) = x ]
Here, (\operatorname{xor}(a_0, a_1, \ldots, a_p)) represents the bitwise XOR of (a_0, a_1, \ldots, a_p) and (\gcd) denotes the greatest common divisor. If no valid index (p) exists, output (-1).

inputFormat

The first line contains two integers \(n\) and \(q\), representing the size of the sequence and the number of operations respectively.

The second line contains \(n\) positive integers: \(a_0, a_1, \ldots, a_{n-1}\) which form the initial sequence.

The following \(q\) lines each contain an operation in one of the following formats:

• MODIFY id x
• QUERY x

Note: Indexing is 0-based.

outputFormat

For each QUERY operation, output a single line containing the smallest index \(p\) for which
\[ \gcd(a_0, a_1, \ldots, a_p) \times \operatorname{xor}(a_0, a_1, \ldots, a_p) = x \] holds. If no such index exists, output \(-1\).

sample

5 5
6 8 3 10 15
QUERY 14
MODIFY 2 7
QUERY 14
QUERY 84
QUERY 36

-1
-1
-1
0