K 主席计划在接下来 $N$ 天内举办一系列会议，每天都会举办恰好一场会议，且会议将在三个场馆之一举行：主场馆 A 或两个副场馆 B 和 C 中的一个。

每场会议的场馆信息由字符串 $S$ 给出，该字符串由 $\mathtt{\text{A}}$、$\mathtt{\text{B}}$、$\mathtt{\text{C}}$ 和 $\mathtt{\text{?}}$ 组成。对于第 $i$ 天（$1\le i\le N$），如果 $S$ 的第 $i$ 个字符是 $\mathtt{\text{A}}$，则会议在场馆 A 举行；如果是 $\mathtt{\text{B}}$，则在场馆 B 举行；如果是 $\mathtt{\text{C}}$，则在场馆 C 举行；如果是 $\mathtt{\text{?}}$，则表示第 $i$ 天的场馆尚未决定。

由于第一天和第 $N$ 天的会议预计会有大量参与者，因此已确定这两天必须使用场馆 A。

现在，K 主席需要为每个未决定的会议分配场馆（每个 $\mathtt{\text{?}}$ 处可以选择 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$
• $⋮$
• $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$ 的数量。

样例一

input

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

output

3
4
4

explanation

在第一个场景中，K 主席需要将 $5$ 个未决定会议中的 $1$ 个分配到场馆 A，$3$ 个分配到 B，$1$ 个分配到 C。例如，一种可能的分配结果会生成场馆信息字符串 $\mathtt{\text{ABBBBCCAA}}$。此时，满足"第 $j$ 天的场馆与第 $(j+1)$ 天的场馆不同"的索引 $j$ 是 $1$、$5$、$7$，共 $3$ 个。由于无法将这个数量减少到 $2$ 或更少，因此第一行的正确输出是 $3$。

在第二个场景中，K 主席需要将 $5$ 个未决定会议中的 $4$ 个分配到 A，$1$ 个分配到 B。例如，一种可能的分配结果会生成字符串 $\mathtt{\text{AAABBACAA}}$。此时，满足条件的索引 $j$ 是 $3$、$5$、$6$、$7$，共 $4$ 个。因此第二行的正确输出是 $4$。

在第三个场景中，K 主席需要将所有 $5$ 个未决定会议分配到 C。满足条件的索引 $j$ 是 $1$、$3$、$4$、$8$，共 $4$ 个。因此第三行的正确输出是 $4$。

该样例满足子任务 $1\sim 5,8$ 的限制。

样例二

input

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

output

4
4
2
2

explanation

该样例满足所有子任务的限制。

样例三

input

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

output

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

explanation

该样例满足子任务 $1,2,4,8$ 的限制。

数据范围

• $2\le N\le 300000$；
• $S$ 是长度为 $N$ 且由 $\mathtt{\text{A}}$、$\mathtt{\text{B}}$、$\mathtt{\text{C}}$ 和 $\mathtt{\text{?}}$ 组成的字符串；
• $S$ 的首字符和末字符均为 $\mathtt{\text{A}}$；
• $1\le Q\le 200000$；
• $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$ 中 $\mathtt{\text{?}}$ 的数量（$1\le k\le Q$）；
• $N$、$Q$、$X_k$、$Y_k$、$Z_k$ 均为整数。

子任务

• $\text{Subtask 1 (4 pts)}$：$N\le 50$ 且 $S$ 中 $\mathtt{\text{?}}$ 的数量不超过 $13$；
• $\text{Subtask 2 (7 pts)}$：$N\le 500$；
• $\text{Subtask 3 (13 pts)}$：$N\le 5000$，$Q\le 10$；
• $\text{Subtask 4 (18 pts)}$：$N\le 5000$；
• $\text{Subtask 5 (12 pts)}$：$Q\le 10$；
• $\text{Subtask 6 (8 pts)}$：$S$ 不含 $\mathtt{\text{C}}$ 且所有 $Z_k=0$（$1\le k\le Q$）；
• $\text{Subtask 7 (13 pts)}$：所有 $Z_k=0$（$1\le k\le Q$）；
• $\text{Subtask 8 (25 pts)}$：无额外限制。