4148: 「HEOI2015」公约数数列
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
设计一个数据结构. 给定一个正整数数列 $a_0, a_1, \ldots , a_{n - 1}$，你需要支持以下两种操作：
1. ``MODIFY id x``: 将 $a_{\text{id}}$ 修改为 $x$.
2. ``QUERY x``: 求最小的整数 $p$ ($0 \leq p < n$)，使得 $\text{gcd}(a_0, a_1, ..., a_p) \cdot \text{XOR}(a_0, a_1, ..., a_p) = x$. 其中 $\text{XOR}(a_0, a_1, ..., a_p)$ 代表 $a_0, a_1, \ldots , a_p$ 的异或和，$\text{gcd}$ 表示最大公约数。
输入
输入数据的第一行包含一个正整数 $n$。
接下来一行包含 $n$ 个正整数 $a_0, a_1, ..., a_{n - 1}$。
之后一行包含一个正整数 $q$，表示询问的个数。
之后 $q$ 行，每行包含一个询问。格式如题目中所述。
输出
对于每个 ``QUERY`` 询问，在单独的一行中输出结果。如果不存在这样的 $p$，输出 ``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提示
数据范围：对于 $100\%$ 的数据，$n \leq 100000, \ q \leq 10000, \ a_i \leq 10^9 (0 \leq i < n)$，``QUERY x`` 中的 $x \leq 10^{18}$，``MODIFY id x`` 中的 $0 \leq \text{id} < n, \ 1 \leq x \leq 10^9$。