← 返回题目列表

Codeforces · 914/D

D. Bash 和一道棘手的数学难题

中文机器翻译题面 查看原题

Bash 喜欢使用数组。他有一个由 n 个整数组成的数组 a1, a2, ... an。他喜欢猜测数组不同部分的最大公约数(gcd)。当然,有时候猜测并不正确。然而,如果他的猜测几乎正确,Bash 就会感到满意。

假设他猜测a的[l,r]范围内元素的gcd为x。如果他最多可以更改段中的一个元素,使得更改后该段的 gcd 为 x,他认为猜测几乎是正确的。请注意,当他猜测时,他实际上并没有更改数组 - 他只是想知道该段的 gcd 是否可以变为 x。除此之外,他有时也会对阵法本身进行一些改动。

由于他自己无法弄清楚,Bash 希望你告诉他他的哪些猜测几乎是正确的。形式上,您必须处理以下形式之一的 q 个查询:

- 1 l r x — Bash 猜测范围 [l, r] 的 gcd 是 x。报告这个猜测是否几乎正确。
- 2 i y — Bash 将 ai 设置为 y。

注意:该数组的索引为 1。

输入

第一行包含一个整数 n (1 ≤ n ≤ 5·105) — 数组的大小。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 109) — 数组的元素。

第三行包含一个整数 q (1 ≤ q ≤ 4·105) — 查询数。

接下来的 q 行描述查询,可能具有以下形式之一:

- 1 l r x(1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109)。
- 2 i y(1 ≤ i ≤ n, 1 ≤ y ≤ 109)。

保证至少有一个第一类型的查询。

输出

对于第一种类型的每个查询,如果 Bash 的猜测几乎正确,则输出“YES”(不带引号),否则输出“NO”(不带引号)。

示例

输入 #1

3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2

输出 #1

YES
YES
NO

输入 #2

5
1 2 3 4 5
6
1 1 4 2
2 3 6
1 1 4 2
1 1 5 2
2 5 10
1 1 5 2

输出 #2

NO
YES
NO
YES

注意

在第一个示例中,数组最初为 {2, 6, 3}。

对于查询 1,前两个数字的 gcd 已经为 2。

对于查询 2,我们可以通过将数组的第一个元素更改为 3 来实现 gcd 为 3。请注意,在类型 1 的查询期间所做的更改是临时的,不会反映在数组中。

查询 3 之后,数组现在为 {9, 6, 3}。

对于查询4,无论更改哪个元素,都无法使范围的gcd为2。