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。