أولئك الذين حلوا مسألة 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