Anda diberikan dua bilangan bulat positif koprima $p$ dan $q$. Terdapat $pq$ jenis kartu berbeda yang dinomori $0, 1, \ldots, pq - 1$.

Terdapat dua tipe paket kartu standar:

• Paket kartu standar Tipe-1: terdapat $p$ macam, dinomori dengan $u$ ($0 \le u < p$). Paket bernomor $u$ berisi satu salinan dari setiap kartu yang nomornya memenuhi $x \equiv u \pmod{p}$, sehingga setiap paket berisi tepat $q$ kartu.
• Paket kartu standar Tipe-2: terdapat $q$ macam, dinomori dengan $v$ ($0 \le v < q$). Paket bernomor $v$ berisi satu salinan dari setiap kartu yang nomornya memenuhi $x \equiv v \pmod{q}$, sehingga setiap paket berisi tepat $p$ kartu.

Sekarang terdapat $n$ kartu yang tersusun di atas meja, dengan nomor kartu ke-$i$ adalah $a_i$. Anda perlu memproses $Q$ operasi dari dua tipe berikut:

• 1 i x: ganti nomor kartu ke-$i$ dengan $x$;
• 2 l r: tentukan apakah semua kartu pada interval $[l, r]$ dapat dipartisi secara tepat menjadi beberapa paket kartu standar.

Catatan: Saat mengemas ulang kartu, setiap kartu pada interval harus termasuk ke dalam tepat satu paket, dan setiap macam paket kartu standar boleh digunakan berapa kali pun.

Masukan

Baris pertama berisi empat bilangan bulat $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$).

Baris kedua berisi $n$ bilangan bulat $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$), yang menyatakan nomor awal dari masing-masing kartu.

$Q$ baris berikutnya masing-masing mendeskripsikan sebuah operasi dalam bentuk 1 i x atau 2 l r:

• Untuk setiap operasi tipe pertama, dijamin bahwa $1 \le i \le n$ dan $0 \le x < pq$.
• Untuk setiap operasi tipe kedua, dijamin bahwa $1 \le l \le r \le n$.

Keluaran

Untuk setiap operasi tipe kedua, jika kartu-kartu yang ditentukan dapat dipartisi secara tepat menjadi beberapa paket kartu standar, keluarkan YES; jika tidak, keluarkan NO.

Contoh

Masukan 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

Keluaran 1

YES
NO
NO
YES

Catatan

Ketika $p = 2, q = 3$:

• Terdapat dua paket kartu standar Tipe-1: $\{0, 2, 4\}$ dan $\{1, 3, 5\}$.
• Terdapat tiga paket kartu standar Tipe-2: $\{0, 3\}$, $\{1, 4\}$, dan $\{2, 5\}$.

Untuk kueri pertama, multiset kartu pada interval adalah $\{0, 0, 2, 3, 4\}$. Multiset tersebut dapat dipartisi menjadi $\{0, 2, 4\} + \{0, 3\}$, sehingga jawabannya adalah YES.

Untuk kueri terakhir, multiset kartu pada interval adalah $\{1, 4\}$. Multiset tersebut membentuk tepat satu paket kartu standar Tipe-2, sehingga jawabannya adalah YES.