問題文

Conference を解いた人は、自然にこの問題を思いついているかもしれません。

長さ N の文字列 S が与えられます。ここで、S の各文字は A, B, C, ? のいずれかであり、特に S の 1 文字目と N 文字目は A です。

ここで、各文字が A, B, C のいずれかである長さ N の文字列のスコアを、文字列の i 文字目と i+1 文字目が異なるような整数 i \ (1 \leq i \leq 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, Q, X_i, Y_i, Z_i は整数
• 2 \leq N \leq 3 \times 10^5
• S は A, B, C, ? からなる長さ N の文字列
• S の 1 文字目と N 文字目は A
• 1 \leq Q \leq 2 \times 10^5
• 0 \leq X_i
• 0 \leq Y_i
• 0 \leq 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

• 1 番目のクエリでは、ABCBABCBA と置き換えればスコアを 8 とできます。
• 2 番目のクエリでは、ABABAACAA と置き換えればスコアを 6 とできます。
• 3 番目のクエリでは、ACCBCCCCA と置き換えればスコアを 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