解决过 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$ 是一个长度为 $N$ 的字符串，由 A、B、C 和 ? 组成。
• $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