Quienes hayan resuelto Conference* pueden llegar naturalmente a plantearse este problema.
Se te da una cadena $S$ de longitud $N$. Cada carácter de $S$ es uno de A, B, C o ?. En particular, el primer y el último carácter de $S$ son A.
Para una cadena de longitud $N$ que consta únicamente de A, B y C, se define su puntuación como el número de enteros $i$ ($1 \le i \le N - 1$) tales que el $i$-ésimo carácter y el $(i + 1)$-ésimo carácter son diferentes.
Se te dan $Q$ consultas. La $i$-ésima consulta es la siguiente:
Se dan enteros no negativos $X_i, Y_i, Z_i$, donde $X_i + Y_i + Z_i$ es igual al número de caracteres ? en $S$. Entre todas las cadenas obtenidas al reemplazar $X_i$ de los caracteres ? en $S$ por A, $Y_i$ de ellos por B y $Z_i$ de ellos por C, imprime la puntuación máxima posible.
Entrada
La entrada se proporciona en el siguiente formato:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Salida
Imprime $Q$ líneas. En la $i$-ésima línea, imprime la respuesta a la $i$-ésima consulta.
Restricciones
- $N, Q, X_i, Y_i, Z_i$ son enteros.
- $2 \le N \le 3 \times 10^5$
- $S$ es una cadena de longitud $N$ formada por
A,B,Cy?. - El primer y el último carácter de $S$ son
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$ es igual al número de caracteres
?en $S$.
Ejemplos
Entrada 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Salida 1
8 6 4
Entrada 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Salida 2
4 8 4 10
Entrada 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
Salida 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
Nota
En el primer ejemplo:
- Para la primera consulta, reemplazar los caracteres como
ABCBABCBAproduce una puntuación de $8$, que es la máxima posible. - Para la segunda consulta, reemplazar los caracteres como
ABABAACAAproduce una puntuación de $6$. - Para la tercera consulta, reemplazar los caracteres como
ACCBCCCCAproduce una puntuación de $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf