Description

Design a data structure. Given a sequence of positive integers $a_0, a_1, \cdots, a_{n - 1}$, you need to support the following two operations:

1. $\text{\texttt{MODIFY} \textit{id} \textit{x}}$: set $a_{id}$ to $x$.
2. $\text{\texttt{QUERY} \textit{x}}$: find the smallest integer $p$ ($0 \le p < n$) such that $\gcd(a_0, a_1, \cdots, a_p) \times \operatorname{xor}(a_0, a_1, \cdots, a_p) = x$. Here $\operatorname{xor}(a_0, a_1, \cdots, a_p)$ denotes the xor-sum of $a_0, a_1, \cdots, a_p$, and $\gcd$ denotes the greatest common divisor.

Input Format

The first line contains a positive integer $n$. The next line contains $n$ positive integers $a_0, a_1, \cdots, a_{n - 1}$. The next line contains a positive integer $q$, the number of queries. Each of the next $q$ lines contains one query, in the format described above.

Output Format

For each $\texttt{QUERY}$, output the result on a separate line. If no such $p$ exists, output no.

10
1353600 5821200 10752000 1670400 3729600 6844320 12544000 117600 59400 640
10
MODIFY 7 20321280
QUERY 162343680
QUERY 1832232960000
MODIFY 0 92160
QUERY 1234567
QUERY 3989856000
QUERY 833018560
MODIFY 3 8600
MODIFY 5 5306112
QUERY 148900352

6
0
no
2
8
8

Hint

Constraints

• For 30% of the testdata, $n \le 10^4$, $q \le 1000$.
• For 100% of the testdata, $n \le 10^5$, $q \le 10000$, $1 \le a_i \le 10^9$, in $\texttt{QUERY}$ operations $x \le 10^{18}$, in modify operations $0 \le id < n$, $1 \le x \le 10^9$.

Translated by ChatGPT 5