Mereka yang telah menyelesaikan Conference* mungkin secara alami akan memikirkan soal ini.
Anda diberikan sebuah string $S$ dengan panjang $N$. Setiap karakter dari $S$ adalah salah satu dari A, B, C, atau ?. Khususnya, karakter pertama dan karakter terakhir dari $S$ adalah A.
Untuk sebuah string dengan panjang $N$ yang hanya terdiri dari A, B, dan C, definisikan skor-nya sebagai banyaknya bilangan bulat $i$ ($1 \le i \le N - 1$) sedemikian sehingga karakter ke-$i$ dan karakter ke-$(i + 1)$ berbeda.
Anda diberikan $Q$ kueri. Kueri ke-$i$ adalah sebagai berikut:
Diberikan bilangan bulat tak negatif $X_i, Y_i, Z_i$, dengan $X_i + Y_i + Z_i$ sama dengan banyaknya karakter ? pada $S$. Di antara semua string yang diperoleh dengan mengganti $X_i$ karakter ? pada $S$ dengan A, $Y_i$ di antaranya dengan B, dan $Z_i$ di antaranya dengan C, keluarkan skor maksimum yang mungkin.
Masukan
Masukan diberikan dalam format berikut:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Keluaran
Keluarkan $Q$ baris. Pada baris ke-$i$, keluarkan jawaban untuk kueri ke-$i$.
Batasan
- $N, Q, X_i, Y_i, Z_i$ adalah bilangan bulat.
- $2 \le N \le 3 \times 10^5$
- $S$ adalah string dengan panjang $N$ yang terdiri dari
A,B,C, dan?. - Karakter pertama dan karakter terakhir dari $S$ adalah
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$ sama dengan banyaknya karakter
?pada $S$.
Contoh
Masukan 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Keluaran 1
8 6 4
Masukan 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Keluaran 2
4 8 4 10
Masukan 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
Keluaran 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
Catatan
Pada contoh pertama:
- Untuk kueri pertama, mengganti karakter menjadi
ABCBABCBAmenghasilkan skor $8$, yang merupakan maksimum yang mungkin. - Untuk kueri kedua, mengganti karakter menjadi
ABABAACAAmenghasilkan skor $6$. - Untuk kueri ketiga, mengganti karakter menjadi
ACCBCCCCAmenghasilkan skor $4$.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf