Ceux qui ont résolu Conference* peuvent naturellement imaginer ce problème.
On vous donne une chaîne de caractères $S$ de longueur $N$. Chaque caractère de $S$ est l'un de A, B, C ou ?. En particulier, le premier et le dernier caractère de $S$ sont A.
Pour une chaîne de longueur $N$ composée uniquement de A, B et C, on définit son score comme le nombre d'entiers $i$ ($1 \le i \le N - 1$) tels que le $i$-ième caractère et le $(i + 1)$-ième caractère soient différents.
On vous donne $Q$ requêtes. La $i$-ième requête est la suivante :
Des entiers non négatifs $X_i, Y_i, Z_i$ sont donnés, où $X_i + Y_i + Z_i$ est égal au nombre de caractères ? dans $S$. Parmi toutes les chaînes obtenues en remplaçant $X_i$ des caractères ? de $S$ par A, $Y_i$ d'entre eux par B et $Z_i$ d'entre eux par C, affichez le score maximum possible.
Entrée
L'entrée est donnée dans le format suivant :
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Sortie
Affichez $Q$ lignes. Sur la $i$-ième ligne, affichez la réponse à la $i$-ième requête.
Contraintes
- $N, Q, X_i, Y_i, Z_i$ sont des entiers.
- $2 \le N \le 3 \times 10^5$
- $S$ est une chaîne de longueur $N$ composée de
A,B,Cet?. - Le premier et le dernier caractère de $S$ sont
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$ est égal au nombre de caractères
?dans $S$.
Exemples
Entrée 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Sortie 1
8 6 4
Entrée 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Sortie 2
4 8 4 10
Entrée 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
Sortie 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
Note
Dans le premier exemple :
- Pour la première requête, remplacer les caractères sous la forme
ABCBABCBAdonne un score de $8$, ce qui est le maximum possible. - Pour la deuxième requête, remplacer les caractères sous la forme
ABABAACAAdonne un score de $6$. - Pour la troisième requête, remplacer les caractères sous la forme
ACCBCCCCAdonne un score de $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf