חפיסות קלפים - 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