P4108 [HEOI2015] Common Divisor Sequence

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.

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.

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

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