[HEOI2015]公约数数列

内存限制：256 MiB 时间限制：10 Sec

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

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

2. QUERY x: 求最小的整数 p (0 <= 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, ..., 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

样例输出

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

#4028. [HEOI2015]公约数数列

题目描述

输入格式

输出格式

样例

样例输入

样例输出

数据范围与提示