P4108 [HEOI2015] 公约数数列

设计一个数据结构. 给定一个正整数数列 $a_0, a_1, \cdots, a_{n - 1}$，你需要支持以下两种操作： 1. $\text{\texttt{MODIFY} \textit{id} \textit{x}}$：将 $a_{id}$ 修改为 $x$； 2. $\text{\texttt{QUERY} \textit{x}}$：求最小的整数 $p \ (0 \le p < n)$，使得 $\gcd(a_0, a_1, \cdots, a_p) \times \operatorname{xor}(a_0, a_1, \cdots, a_p) = x$。其中 $\operatorname{xor}(a_0, a_1, \cdots, a_p)$ 代表 $a_0, a_1, \cdots, a_p$ 的异或和，$\gcd$ 表示最大公约数。

无

无

### 数据范围及约定 - 对于 $30\%$ 的数据，$n\le10^4$，$q\le 1000$。 - 对于 $100\%$ 的数据，$n\le10^5$，$q\le 10000$，$1\le a_i\le 10^9$，询问操作中 $x \le 10^{18}$，修改操作中 $0\le id