#2119. 「HEOI2015」公约数数列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

设计一个数据结构. 给定一个正整数数列 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