Bash và bài toán GCD khó (Bash and a Tough Math Puzzle)

Nguồn: Codeforces

Phiên bản: Phước Hưng OJ Extended

Cho mảng $A_1,A_2,\ldots,A_N$. Có hai loại truy vấn:

• 1 l r x: kiểm tra xem có thể thay đổi không quá một phần tử trong đoạn $[l,r]$ để GCD của cả đoạn trở thành $x$ hay không. Thao tác thay đổi này chỉ là giả định, không làm thay đổi mảng thật.
• 2 i y: gán thật sự $A_i=y$.

Với truy vấn loại 1, in YES nếu có thể và NO nếu không thể.

Input

Dòng đầu chứa $N$.

Dòng thứ hai chứa $A_1,\ldots,A_N$.

Dòng thứ ba chứa $Q$.

$Q$ dòng tiếp theo mô tả truy vấn.

Output

Với mỗi truy vấn loại 1, in YES hoặc NO.

Subtask

• 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$.

Ví dụ

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

Giải thích

Hai truy vấn đầu có thể đạt GCD mong muốn bằng cách đổi không quá một phần tử; truy vấn cuối cần sửa nhiều hơn một phần tử nên in NO.