Bạn được cho hai số nguyên dương nguyên tố cùng nhau $p$ và $q$. Có $pq$ loại thẻ bài khác nhau, được đánh số $0, 1, \ldots, pq - 1$.

Có hai loại gói bài tiêu chuẩn:

• Gói bài tiêu chuẩn loại 1: có $p$ loại, được đánh số bởi $u$ ($0 \le u < p$). Gói được đánh số $u$ chứa một bản sao của mỗi thẻ bài có số hiệu thỏa mãn $x \equiv u \pmod{p}$, vì vậy mỗi gói chứa đúng $q$ thẻ bài.
• Gói bài tiêu chuẩn loại 2: có $q$ loại, được đánh số bởi $v$ ($0 \le v < q$). Gói được đánh số $v$ chứa một bản sao của mỗi thẻ bài có số hiệu thỏa mãn $x \equiv v \pmod{q}$, vì vậy mỗi gói chứa đúng $p$ thẻ bài.

Hiện có $n$ thẻ bài được xếp trên bàn, trong đó số hiệu của thẻ bài thứ $i$ là $a_i$. Bạn cần xử lý $Q$ thao tác thuộc hai loại sau:

• 1 i x: thay số hiệu của thẻ bài thứ $i$ bằng $x$;
• 2 l r: xác định xem tất cả các thẻ bài trong đoạn $[l, r]$ có thể được phân hoạch vừa khít thành một số gói bài tiêu chuẩn hay không.

Ghi chú: Khi đóng gói lại các thẻ bài, mỗi thẻ bài trong đoạn phải thuộc về đúng một gói, và mỗi loại gói bài tiêu chuẩn có thể được sử dụng số lần tùy ý.

Dữ liệu vào

Dòng đầu tiên chứa bốn số nguyên $n, p, q, Q$ ($1 \le n, p, q, Q \le 3 \times 10^5$, $2 \le p + q \le 3 \times 10^5$, $\gcd(p, q) = 1$).

Dòng thứ hai chứa $n$ số nguyên $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), biểu thị số hiệu ban đầu của mỗi thẻ bài.

$Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác dưới dạng 1 i x hoặc 2 l r:

• Đối với mỗi thao tác loại thứ nhất, dữ liệu đảm bảo rằng $1 \le i \le n$ và $0 \le x < pq$.
• Đối với mỗi thao tác loại thứ hai, dữ liệu đảm bảo rằng $1 \le l \le r \le n$.

Dữ liệu ra

Đối với mỗi thao tác loại thứ hai, nếu các thẻ bài được chỉ định có thể được phân hoạch vừa khít thành một số gói bài tiêu chuẩn, hãy in ra YES; ngược lại, in ra NO.

Ví dụ

Dữ liệu vào 1

8 2 3 5
0 0 2 3 4 1 4 2
2 1 5
2 6 8
1 8 5
2 6 8
2 6 7

Dữ liệu ra 1

YES
NO
NO
YES

Ghi chú

Khi $p = 2, q = 3$:

• Có hai gói bài tiêu chuẩn loại 1: $\{0, 2, 4\}$ và $\{1, 3, 5\}$.
• Có ba gói bài tiêu chuẩn loại 2: $\{0, 3\}$, $\{1, 4\}$ và $\{2, 5\}$.

Đối với truy vấn đầu tiên, tập hợp bội của các thẻ bài trong đoạn là $\{0, 0, 2, 3, 4\}$. Nó có thể được phân hoạch thành $\{0, 2, 4\} + \{0, 3\}$, vì vậy câu trả lời là YES.

Đối với truy vấn cuối cùng, tập hợp bội của các thẻ bài trong đoạn là $\{1, 4\}$. Nó tạo thành đúng một gói bài tiêu chuẩn loại 2, vì vậy câu trả lời là YES.