CF914D.Bash and a Tough Math Puzzle

Bash likes playing with arrays. He has an array _a_1, _a_2, ... a__n of n integers. He likes to guess the greatest common divisor (gcd) of different segments of the array. Of course, sometimes the guess is not correct. However, Bash will be satisfied if his guess is almost correct.

Suppose he guesses that the gcd of the elements in the range [l, r] of a is x. He considers the guess to be almost correct if he can change at most one element in the segment such that the gcd of the segment is x after making the change. Note that when he guesses, he doesn't actually change the array — he just wonders if the gcd of the segment can be made x. Apart from this, he also sometimes makes changes to the array itself.

Since he can't figure it out himself, Bash wants you to tell him which of his guesses are almost correct. Formally, you have to process q queries of one of the following forms:

• 1 l r x — Bash guesses that the gcd of the range [l, r] is x. Report if this guess is almost correct.
• 2 i y — Bash sets a__i to y.

Note: The array is 1-indexed.

Bash 喜欢玩数组。他有一个包含 $n$ 个整数的数组 $a_1, a_2, \dots, a_n$。他喜欢猜测数组不同区间的最大公约数（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 将 $a_i$ 修改为 $y$。

注意：数组下标从 1 开始。

The first line contains an integer n (1 ≤ n ≤ 5·105) — the size of the array.

The second line contains n integers _a_1, _a_2, ..., a__n (1 ≤ a__i ≤ 109) — the elements of the array.

The third line contains an integer q (1 ≤ q ≤ 4·105) — the number of queries.

The next q lines describe the queries and may have one of the following forms:

• 1 l r x (1 ≤ l ≤ r ≤ n, 1 ≤ x ≤ 109).
• 2 i y (1 ≤ i ≤ n, 1 ≤ y ≤ 109).

Guaranteed, that there is at least one query of first type.

第一行包含一个整数 $n$（$1 \leq n \leq 5\cdot10^5$）—— 数组的大小。

第二行包含 $n$ 个整数 $a_1,\,a_2,\,\dots,\,a_n$（$1 \leq a_i \leq 10^9$）—— 数组的元素。

第三行包含一个整数 $q$（$1 \leq q \leq 4\cdot10^5$）—— 查询的数量。

接下来的 $q$ 行描述查询，每行是以下两种形式之一：

• 1 l r x（其中 $1 \leq l \leq r \leq n$，$1 \leq x \leq 10^9$）；
• 2 i y（其中 $1 \leq i \leq n$，$1 \leq y \leq 10^9$）。

保证至少存在一个第一类查询。

For each query of first type, output "YES" (without quotes) if Bash's guess is almost correct and "NO" (without quotes) otherwise.

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

In the first sample, the array initially is {2, 6, 3}.

For query 1, the first two numbers already have their gcd as 2.

For query 2, we can achieve a gcd of 3 by changing the first element of the array to 3. Note that the changes made during queries of type 1 are temporary and do not get reflected in the array.

After query 3, the array is now {9, 6, 3}.

For query 4, no matter which element you change, you cannot get the gcd of the range to be 2.

在第一个样例中，数组初始为 $\{2,\,6,\,3\}$。

对于查询 1，前两个数的 $\gcd$ 已经是 $2$。

对于查询 2，我们可以通过将数组的第一个元素改为 $3$ 来使 $\gcd$ 达到 $3$。注意：类型 1 的查询所作的修改是临时的，不会反映到原数组中。

查询 3 之后，数组变为 $\{9,\,6,\,3\}$。

对于查询 4，无论修改哪个元素，都无法使该区间内的 $\gcd$ 变为 $2$。