Wer Conference* gelöst hat, kommt vielleicht ganz natürlich auf dieses Problem.
Gegeben ist eine Zeichenkette $S$ der Länge $N$. Jedes Zeichen von $S$ ist eines von A, B, C oder ?. Insbesondere sind das erste und das letzte Zeichen von $S$ gleich A.
Für eine Zeichenkette der Länge $N$, die nur aus A, B und C besteht, definieren wir ihre Punktzahl als die Anzahl der ganzen Zahlen $i$ ($1 \le i \le N - 1$), sodass das $i$-te Zeichen und das $(i + 1)$-te Zeichen verschieden sind.
Dir werden $Q$ Anfragen gestellt. Die $i$-te Anfrage lautet wie folgt:
Nichtnegative ganze Zahlen $X_i, Y_i, Z_i$ sind gegeben, wobei $X_i + Y_i + Z_i$ gleich der Anzahl der ?-Zeichen in $S$ ist. Gib unter allen Zeichenketten, die man erhält, indem man $X_i$ der ?-Zeichen in $S$ durch A, $Y_i$ davon durch B und $Z_i$ davon durch C ersetzt, die maximal mögliche Punktzahl aus.
Eingabe
Die Eingabe erfolgt im folgenden Format:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Ausgabe
Gib $Q$ Zeilen aus. Gib in der $i$-ten Zeile die Antwort auf die $i$-te Anfrage aus.
Bedingungen
- $N, Q, X_i, Y_i, Z_i$ sind ganze Zahlen.
- $2 \le N \le 3 \times 10^5$
- $S$ ist eine Zeichenkette der Länge $N$, bestehend aus
A,B,Cund?. - Das erste und das letzte Zeichen von $S$ sind
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$ ist gleich der Anzahl der
?-Zeichen in $S$.
Beispiele
Eingabe 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Ausgabe 1
8 6 4
Eingabe 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Ausgabe 2
4 8 4 10
Eingabe 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
Ausgabe 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
Hinweis
Im ersten Beispiel:
- Für die erste Anfrage liefert das Ersetzen der Zeichen zu
ABCBABCBAeine Punktzahl von $8$, was das mögliche Maximum ist. - Für die zweite Anfrage liefert das Ersetzen der Zeichen zu
ABABAACAAeine Punktzahl von $6$. - Für die dritte Anfrage liefert das Ersetzen der Zeichen zu
ACCBCCCCAeine Punktzahl von $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf