Conference* есебін шығарғандар бұл есепті де табиғи түрде ойлап табуы мүмкін.
Сізге ұзындығы $N$ болатын $S$ жолы берілген. $S$ жолының әрбір таңбасы — A, B, C немесе ? таңбаларының бірі. Атап айтқанда, $S$ жолының бірінші және соңғы таңбалары A болып табылады.
Тек A, B және C таңбаларынан тұратын ұзындығы $N$ жол үшін оның ұпайын $i$-ші таңба мен $(i + 1)$-ші таңба әртүрлі болатындай $i$ ($1 \le i \le N - 1$) бүтін сандарының саны ретінде анықтаймыз.
Сізге $Q$ сұраныс берілген. $i$-ші сұраныс келесідей:
Теріс емес $X_i, Y_i, Z_i$ бүтін сандары берілген, мұндағы $X_i + Y_i + Z_i$ қосындысы $S$ жолындағы ? таңбаларының санына тең. $S$ жолындағы ? таңбаларының $X_i$ данасын A таңбасымен, $Y_i$ данасын B таңбасымен және $Z_i$ данасын C таңбасымен алмастыру арқылы алынған барлық жолдардың ішінен мүмкін болатын ең үлкен ұпайды шығарыңыз.
Кіріс деректер
Кіріс деректер келесі форматта беріледі:
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 : X_Q Y_Q Z_Q
Шығыс деректер
$Q$ жол шығарыңыз. $i$-ші жолда $i$-ші сұраныстың жауабын шығарыңыз.
Шектеулер
- $N, Q, X_i, Y_i, Z_i$ — бүтін сандар.
- $2 \le N \le 3 \times 10^5$
- $S$ —
A,B,Cжәне?таңбаларынан тұратын ұзындығы $N$ жол. - $S$ жолының бірінші және соңғы таңбалары —
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$ қосындысы $S$ жолындағы
?таңбаларының санына тең.
Мысалдар
Кіріс 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
Шығыс 1
8 6 4
Кіріс 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
Шығыс 2
4 8 4 10
Кіріс 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
Шығыс 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
Ескертпе
Бірінші мысалда:
- Бірінші сұраныс үшін таңбаларды
ABCBABCBAетіп алмастыру $8$ ұпай береді, бұл мүмкін болатын ең үлкен мән. - Екінші сұраныс үшін таңбаларды
ABABAACAAетіп алмастыру $6$ ұпай береді. - Үшінші сұраныс үшін таңбаларды
ACCBCCCCAетіп алмастыру $4$ ұпай береді.
* https://www2.ioi-jp.org/camp/2025/2025-sp-tasks/contest3/conference-en.pdf