Bash and a Tough Math Puzzle
Contest: Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined)
Difficulty rating: 1900
Tags: data structures, number theory

Bash likes playing with arrays. He has an array a1, a2, ... an 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 ai to y.

Note: The array is 1-indexed.

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

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 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.

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

Constraints:
Time limit: 2.5 s
Memory limit: 256.0 MB

Note:
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.

Example input:
3
2 6 3
4
1 1 2 2
1 1 3 3
2 1 9
1 1 3 2

Example output:
YES
YES
NO

Example input:
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

Example output:
NO
YES
NO
YES

Editorial:
Build a segment tree on the array to answer range gcd queries. We can handle single element updates in the segment tree. Let us see how to answer an (l, r, x) query.
The segment tree decomposes the query range into O(logn) nodes that cover the range. If the gcds of all of these nodes are multiples of x, then the answer is YES. If the gcd of two or more of these nodes is not a multiple of x, then the answer is NO.
If the gcd of exactly one node is not a multiple of x, then we need to know how many elements in this node are not multiples of x. We can find this by traversing the descendents of that node.
If at a point only one child is not a multiple of x, recurse into it. If at any point, there are two children whose gcds are not multiples of x, then the answer is NO. Otherwise, if we reach a node that doesn't have any children, then the answer is YES.