מי שפתר את Conference* עשוי להגיע לבעיה זו באופן טבעי.
נתונה לך מחרוזת $S$ באורך $N$. כל תו של $S$ הוא אחד מבין A, B, C או ?. בפרט, התו הראשון והתו האחרון של $S$ הם A.
עבור מחרוזת באורך $N$ המורכבת רק מ-A, B ו-C, נגדיר את הניקוד שלה כמספר השלמים $i$ ($1 \le i \le N - 1$) כך שהתו ה-$i$ והתו ה-$(i + 1)$ שונים זה מזה.
נתונות לך $Q$ שאילתות. השאילתה ה-$i$ היא כדלקמן:
נתונים מספרים שלמים אי-שליליים $X_i, Y_i, Z_i$, כאשר $X_i + Y_i + Z_i$ שווה למספר התווים ? ב-$S$. מבין כל המחרוזות המתקבלות על ידי החלפת $X_i$ מתווי ? ב-$S$ ב-A, $Y_i$ מהם ב-B, ו-$Z_i$ מהם ב-C, הדפס את הניקוד המקסימלי האפשרי.
קלט
הקלט ניתן בפורמט הבא:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
פלט
הדפס $Q$ שורות. בשורה ה-$i$, הדפס את התשובה לשאילתה ה-$i$.
אילוצים
- $N, Q, X_i, Y_i, Z_i$ הם מספרים שלמים.
- $2 \le N \le 3 \times 10^5$
- $S$ היא מחרוזת באורך $N$ המורכבת מ-
A,B,Cו-?. - התו הראשון והתו האחרון של $S$ הם
A. - $1 \le Q \le 2 \times 10^5$
- $0 \le X_i$
- $0 \le Y_i$
- $0 \le Z_i$
- $X_i + Y_i + Z_i$ שווה למספר התווים
?ב-$S$.
דוגמאות
קלט 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
פלט 1
8 6 4
קלט 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
פלט 2
4 8 4 10
קלט 3
28 ACB??B???BCB??B????B?AAA?BBA 26 6 1 6 4 5 4 2 3 8 9 2 2 11 0 2 8 4 1 11 0 2 2 0 11 0 1 12 12 1 0 10 3 0 1 4 8 3 7 3 2 8 3 1 3 9 11 1 1 7 0 6 6 4 3 8 4 1 0 10 3 13 0 0 11 1 1 0 6 7 2 8 3 9 0 4 0 0 13
פלט 3
24 21 23 21 19 20 19 21 19 17 19 22 19 17 22 19 23 22 20 13 15 19 20 17 21 17
הערה
בדוגמה הראשונה:
- עבור השאילתה הראשונה, החלפת התווים ל-
ABCBABCBAמניבה ניקוד של $8$, שהוא המקסימום האפשרי. - עבור השאילתה השנייה, החלפת התווים ל-
ABABAACAAמניבה ניקוד של $6$. - עבור השאילתה השלישית, החלפת התווים ל-
ACCBCCCCAמניבה ניקוד של $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf