De som har løst Conference*, vil naturlig nok kunne komme på dette problemet.
Du får gitt en streng $S$ med lengde $N$. Hvert tegn i $S$ er ett av A, B, C eller ?. Spesielt er det første og det siste tegnet i $S$ lik A.
For en streng med lengde $N$ som kun består av A, B og C, definerer vi poengsummen dens som antallet heltall $i$ ($1 \le i \le N - 1$) slik at det $i$-te tegnet og det $(i + 1)$-te tegnet er forskjellige.
Du får gitt $Q$ spørringer. Den $i$-te spørringen er som følger:
Ikke-negative heltall $X_i, Y_i, Z_i$ er gitt, der $X_i + Y_i + Z_i$ er lik antallet ?-tegn i $S$. Blant alle strenger som oppnås ved å erstatte $X_i$ av ?-tegnene i $S$ med A, $Y_i$ av dem med B og $Z_i$ av dem med C, skriv ut den maksimalt mulige poengsummen.
Inndata
Inndataene gis på følgende format:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Utdata
Skriv ut $Q$ linjer. På den $i$-te linjen skal du skrive ut svaret på den $i$-te spørringen.
Begrensninger
- $N, Q, X_i, Y_i, Z_i$ er heltall.
- $2 \le N \le 3 \times 10^5$
- $S$ er en streng med lengde $N$ som består av
A,B,Cog?. - Det første og det siste tegnet i $S$ er
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$ er lik antallet
?-tegn i $S$.
Eksempler
Inndata 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Utdata 1
8 6 4
Inndata 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Utdata 2
4 8 4 10
Inndata 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
Utdata 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
Merk
I det første eksempelet:
- For den første spørringen gir det å erstatte tegnene som
ABCBABCBAen poengsum på $8$, som er det maksimalt mulige. - For den andre spørringen gir det å erstatte tegnene som
ABABAACAAen poengsum på $6$. - For den tredje spørringen gir det å erstatte tegnene som
ACCBCCCCAen poengsum på $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf