[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$ 表示最大公约数。

输入输出格式

输入格式


第一行包含一个正整数 $n$。 接下来一行包含 $n$ 个正整数 $a_0,a_1,\cdots,a_{n-1}$。 之后一行包含一个正整数 $q$,表示询问的个数。 之后 $q$ 行,每行包含一个询问。格式如题目中所述。

输出格式


对于每个 $\texttt{QUERY}$ 询问,在单独的一行中输出结果。如果不存在这样的 $p$,输出 `no`。

输入输出样例

输入样例 #1

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

输出样例 #1

6
0
no
2
8
8

说明

### 数据范围及约定 - 对于 $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<n$,$1\le x\le 10^9$。