Ті, хто розв'язав задачу 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