Bash and a Tough Math Puzzle

Source: Codeforces

Version: Phuoc Hung OJ Extended

Given an array $A_1,A_2,\ldots,A_N$, process two query types:

• 1 l r x: determine whether changing at most one element of $[l,r]$ could make the gcd of the segment equal to $x$. This hypothetical change does not modify the stored array.
• 2 i y: actually assign $A_i=y$.

For each type 1 query, print YES if the guess is almost correct and NO otherwise.

Input

The first line contains $N$.

The second line contains $A_1,\ldots,A_N$.

The third line contains $Q$.

The next $Q$ lines describe the queries.

Output

For each type 1 query, print YES or NO.

Subtasks

• Subtask 1 — 20%: $1\le N,Q\le 50$, $1\le A_i,x,y\le 10^4$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$, $1\le A_i,x,y\le 10^9$.
• Subtask 3 — 50%: $1\le N\le 5\cdot10^5$, $1\le Q\le 4\cdot10^5$, $1\le A_i,x,y\le 10^9$.

Examples

Input

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

Output

YES
YES
NO

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.