Osoby, które rozwiązały zadanie Conference*, mogą w naturalny sposób wpaść na ten problem.
Dany jest napis $S$ o długości $N$. Każdy znak napisu $S$ to A, B, C lub ?. W szczególności pierwszy i ostatni znak napisu $S$ to A.
Dla napisu o długości $N$ składającego się wyłącznie ze znaków A, B oraz C definiujemy jego wynik jako liczbę takich liczb całkowitych $i$ ($1 \le i \le N - 1$), że $i$-ty znak oraz $(i + 1)$-szy znak są różne.
Danych jest $Q$ zapytań. $i$-te zapytanie wygląda następująco:
Dane są nieujemne liczby całkowite $X_i, Y_i, Z_i$, gdzie $X_i + Y_i + Z_i$ równa się liczbie znaków ? w napisie $S$. Spośród wszystkich napisów uzyskanych przez zastąpienie $X_i$ znaków ? w $S$ znakiem A, $Y_i$ z nich znakiem B oraz $Z_i$ z nich znakiem C, wypisz maksymalny możliwy wynik.
Wejście
Wejście jest podane w następującym formacie:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Wyjście
Wypisz $Q$ wierszy. W $i$-tym wierszu wypisz odpowiedź na $i$-te zapytanie.
Ograniczenia
- $N, Q, X_i, Y_i, Z_i$ są liczbami całkowitymi.
- $2 \le N \le 3 \times 10^5$
- $S$ jest napisem o długości $N$ składającym się ze znaków
A,B,Coraz?. - Pierwszy i ostatni znak napisu $S$ to
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$ równa się liczbie znaków
?w napisie $S$.
Przykłady
Wejście 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Wyjście 1
8 6 4
Wejście 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Wyjście 2
4 8 4 10
Wejście 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
Wyjście 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
Uwaga
W pierwszym przykładzie:
- Dla pierwszego zapytania zastąpienie znaków tak, by powstał napis
ABCBABCBA, daje wynik $8$, co jest maksymalną możliwą wartością. - Dla drugiego zapytania zastąpienie znaków tak, by powstał napis
ABABAACAA, daje wynik $6$. - Dla trzeciego zapytania zastąpienie znaków tak, by powstał napis
ACCBCCCCA, daje wynik $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf