题目描述

设计一个数据结构. 给定一个正整数数列 $a_0, a_1, ..., a_{n - 1}$，你需要支持以下两种操作：

1. MODIFY id x: 将 $a_{id}$ 修改为 x.

2. QUERY x: 求最小的整数 $p (0 \le p < n)$，使得 $gcd(a_0, a_1, ..., a_p) * XOR(a_0, a_1, ..., a_p) = x$. 其中 $XOR(a_0, a_1, ..., a_p)$ 代表 $a_0, a_1, \cdots, a_p$ 的异或和，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

提示

对于 30% 的数据，$n \le 10000$，$q \le 1000$.

对于 100% 的数据，$n \le 100000$，$q \le 10000$，$a_i \le 10^9 (0 \le i < n)$，QUERY x 中的 $x \le 10^{18}$，MODIFY id x 中的 $0 \le id < n$，$1 \le x \le 10^9$.