F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 4028. -- [HEOI2015]公约数数列

4028: [HEOI2015]公约数数列

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1266  Solved: 484
[Submit][Status][Discuss]

Description

设计一个数据结构. 给定一个正整数数列 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表示最大公约数。

Input

 输入数据的第一行包含一个正整数 n.

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

Output

对于每个 QUERY 询问,在单独的一行中输出结果。如果不存在这样的 p,输出 no.

Sample Input

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

Sample Output

6
0
no
2
8
8

HINT

 对于 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.


Source

[Submit][Status][Discuss]

HOME Back