Chi ha risolto Conference* potrebbe pensare naturalmente a questo problema.
Ti viene data una stringa $S$ di lunghezza $N$. Ogni carattere di $S$ è uno tra A, B, C o ?. In particolare, il primo e l'ultimo carattere di $S$ sono A.
Per una stringa di lunghezza $N$ composta solo da A, B e C, definiamo il suo punteggio come il numero di interi $i$ ($1 \le i \le N - 1$) tali che l'$i$-esimo carattere e l'$(i + 1)$-esimo carattere siano diversi.
Ti vengono date $Q$ query. L'$i$-esima query è la seguente:
Vengono dati gli interi non negativi $X_i, Y_i, Z_i$, dove $X_i + Y_i + Z_i$ è uguale al numero di caratteri ? in $S$. Tra tutte le stringhe ottenute sostituendo $X_i$ dei caratteri ? in $S$ con A, $Y_i$ di essi con B e $Z_i$ di essi con C, stampa il punteggio massimo possibile.
Input
L'input è fornito nel seguente formato:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Output
Stampa $Q$ righe. Sulla $i$-esima riga, stampa la risposta alla $i$-esima query.
Vincoli
- $N, Q, X_i, Y_i, Z_i$ sono interi.
- $2 \le N \le 3 \times 10^5$
- $S$ è una stringa di lunghezza $N$ composta da
A,B,Ce?. - Il primo e l'ultimo carattere di $S$ sono
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$ è uguale al numero di caratteri
?in $S$.
Esempi
Input 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Output 1
8 6 4
Input 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Output 2
4 8 4 10
Input 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
Output 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
Nel primo esempio:
- Per la prima query, sostituendo i caratteri come
ABCBABCBAsi ottiene un punteggio di $8$, che è il massimo possibile. - Per la seconda query, sostituendo i caratteri come
ABABAACAAsi ottiene un punteggio di $6$. - Per la terza query, sostituendo i caratteri come
ACCBCCCCAsi ottiene un punteggio di $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf