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