يُعطى لك عددان صحيحان موجبان أوليان نسبيًا $p$ و $q$. يوجد $pq$ نوعًا مختلفًا من البطاقات، مرقمة $0, 1, \ldots, pq - 1$.
يوجد نوعان من حزم البطاقات القياسية:
- حزم البطاقات القياسية من النوع 1: يوجد منها $p$ أصناف، مرقمة بالعدد $u$ ($0 \le u < p$). تحتوي الحزمة المرقمة بـ $u$ على نسخة واحدة من كل بطاقة يحقق رقمها $x \equiv u \pmod{p}$، ولذلك تحتوي كل حزمة على $q$ بطاقات بالضبط.
- حزم البطاقات القياسية من النوع 2: يوجد منها $q$ أصناف، مرقمة بالعدد $v$ ($0 \le v < q$). تحتوي الحزمة المرقمة بـ $v$ على نسخة واحدة من كل بطاقة يحقق رقمها $x \equiv v \pmod{q}$، ولذلك تحتوي كل حزمة على $p$ بطاقات بالضبط.
توجد الآن $n$ بطاقات مرتبة على الطاولة، حيث رقم البطاقة $i$ هو $a_i$. عليك معالجة $Q$ عمليات من النوعين التاليين:
1 i x: استبدل رقم البطاقة $i$ بالقيمة $x$؛2 l r: حدد ما إذا كان يمكن تقسيم جميع البطاقات في المجال $[l, r]$ بالضبط إلى عدة حزم بطاقات قياسية.
ملاحظة: عند إعادة تعبئة البطاقات، يجب أن تنتمي كل بطاقة في المجال إلى حزمة واحدة بالضبط، ويمكن استخدام كل صنف من حزم البطاقات القياسية أي عدد من المرات.
الإدخال
يحتوي السطر الأول على أربعة أعداد صحيحة $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$).
يحتوي السطر الثاني على $n$ أعداد صحيحة $a_1, a_2, \ldots, a_n$ ($0 \le a_i < pq$)، تمثل الرقم الابتدائي لكل بطاقة.
تصف الأسطر الـ $Q$ التالية كل منها عملية على الصورة 1 i x أو 2 l r:
- لكل عملية من النوع الأول، يُضمن أن $1 \le i \le n$ و $0 \le x < pq$.
- لكل عملية من النوع الثاني، يُضمن أن $1 \le l \le r \le n$.
الإخراج
لكل عملية من النوع الثاني، إذا كان يمكن تقسيم البطاقات المحددة بالضبط إلى عدة حزم بطاقات قياسية، فاطبع YES؛ وإلا فاطبع NO.
أمثلة
الإدخال 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
الإخراج 1
YES NO NO YES
ملاحظة
عندما $p = 2, q = 3$:
- توجد حزمتان قياسيتان من النوع 1: $\{0, 2, 4\}$ و $\{1, 3, 5\}$.
- توجد ثلاث حزم قياسية من النوع 2: $\{0, 3\}$ و $\{1, 4\}$ و $\{2, 5\}$.
بالنسبة للاستعلام الأول، المجموعة المتعددة للبطاقات في المجال هي $\{0, 0, 2, 3, 4\}$. يمكن تقسيمها إلى $\{0, 2, 4\} + \{0, 3\}$، ولذلك فإن الإجابة هي YES.
بالنسبة للاستعلام الأخير، المجموعة المتعددة للبطاقات في المجال هي $\{1, 4\}$. وهي تشكل بالضبط حزمة بطاقات قياسية واحدة من النوع 2، ولذلك فإن الإجابة هي YES.