K 主席计划在 $N$ 天内举办一系列会议。每天恰好举办一场会议，会议将在三个场馆之一举行：主场馆 A 或分场馆 B 和 C。

每场会议的场馆信息由一个由 'A'、'B'、'C' 和 '?' 组成的字符串 $S$ 给出。对于第 $i$ 天（$1 \le i \le N$），如果 $S$ 的第 $i$ 个字符是 'A'，则会议在场馆 A 举行；如果是 'B'，则在场馆 B 举行；如果是 'C'，则在场馆 C 举行；如果是 '?'，则第 $i$ 天的场馆尚未确定。然而，由于第一天和第 $N$ 天的会议预计会有许多参与者，因此已经确定这两天将使用场馆 A。

K 主席现在需要为每个未确定的会议分配一个场馆，从 A、B、C 中选择一个。此外，为了尽量减少在场馆之间移动的负担，他希望最小化满足以下条件的索引 $j$ ($1 \le j \le N - 1$) 的数量：第 $j$ 天的场馆与第 $(j + 1)$ 天的场馆不同。

关于场馆分配有 $Q$ 个场景需要考虑。第 $k$ 个场景（$1 \le k \le Q$）及其对应的问题如下：

• K 主席必须将 $X_k$ 个未确定的会议分配给场馆 A，$Y_k$ 个分配给场馆 B，$Z_k$ 个分配给场馆 C。确定第 $j$ 天的场馆与第 $(j + 1)$ 天的场馆不同的索引 $j$ 的最小可能数量。

给定有关场馆的信息和需要考虑的场景，编写一个程序来回答这些问题。

输入格式

从标准输入读取以下数据：

$N$ $S$ $Q$ $X_1 \ Y_1 \ Z_1$ $X_2 \ Y_2 \ Z_2$ $\vdots$ $X_Q \ Y_Q \ Z_Q$

输出格式

向标准输出写入 $Q$ 行。在第 $k$ 行（$1 \le k \le Q$）中，输出在 K 主席将 $X_k$ 个未确定会议分配给场馆 A，$Y_k$ 个分配给场馆 B，$Z_k$ 个分配给场馆 C 的条件下，第 $j$ 天的场馆与第 $(j + 1)$ 天的场馆不同的索引 $j$ 的最小数量。

数据范围

• $2 \le N \le 300\,000$。
• $S$ 是一个长度为 $N$ 的字符串，由 'A'、'B'、'C' 和 '?' 组成。
• $S$ 的第一个和第 $N$ 个字符是 'A'。
• $1 \le Q \le 200\,000$。
• $0 \le X_k$ ($1 \le k \le Q$)。
• $0 \le Y_k$ ($1 \le k \le Q$)。
• $0 \le Z_k$ ($1 \le k \le Q$)。
• $X_k + Y_k + Z_k$ 等于 $S$ 中 '?' 的数量 ($1 \le k \le Q$)。
• $N, Q, X_k, Y_k, Z_k$ 均为整数。

子任务

1. (4 分) $N \le 50$ 且 $S$ 中 '?' 的数量小于或等于 13。
2. (7 分) $N \le 500$。
3. (13 分) $N \le 5\,000, Q \le 10$。
4. (18 分) $N \le 5\,000$。
5. (12 分) $Q \le 10$。
6. (8 分) $S$ 不包含 'C' 且 $Z_k = 0$ ($1 \le k \le Q$)。
7. (13 分) $Z_k = 0$ ($1 \le k \le Q$)。
8. (25 分) 无附加限制。

样例

样例输入 1

9
A??B??C?A
3
1 3 1
4 1 0
0 0 5

样例输出 1

3
4
4

样例输入 2

12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0

样例输出 2

4
4
2
2

样例输入 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

15
11
13
13
15
12
15
15
16
15
13
12
10
9
13
15
15
11
12
9
15
15
11
9
15
17