ซองการ์ด - Problem

กำหนดจำนวนเต็มบวกสองจำนวนที่เป็นจำนวนเฉพาะสัมพัทธ์กัน $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:

สำหรับการดำเนินการประเภทที่สองแต่ละครั้ง หากการ์ดที่ระบุสามารถแบ่งออกเป็นซองการ์ดมาตรฐานจำนวนหนึ่งได้ลงตัวพอดี ให้แสดงผล YES มิฉะนั้นให้แสดงผล NO

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

YES
NO
NO
YES

เมื่อ $p = 2, q = 3$:

สำหรับคำถามแรก มัลติเซตของการ์ดในช่วงคือ $\{0, 0, 2, 3, 4\}$ ซึ่งสามารถแบ่งออกเป็น $\{0, 2, 4\} + \{0, 3\}$ ได้ ดังนั้นคำตอบจึงเป็น YES

สำหรับคำถามสุดท้าย มัลติเซตของการ์ดในช่วงคือ $\{1, 4\}$ ซึ่งประกอบเป็นซองการ์ดมาตรฐานประเภทที่ 2 จำนวนหนึ่งซองพอดี ดังนั้นคำตอบจึงเป็น YES

QOJ.ac