#212053. [JOIST 2025] 大会 / Conference

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

每场会议的场馆信息由字符串 给出，该字符串由 、、 和 组成。对于第 天（），如果 的第 个字符是 ，则会议在场馆 A 举行；如果是 ，则在场馆 B 举行；如果是 ，则在场馆 C 举行；如果是 ，则表示第 天的场馆尚未决定。

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

现在，K 主席需要为每个未决定的会议分配场馆（每个 处可以选择 A、B 或 C）。此外，为了最小化场馆间移动的负担，他希望最小化满足以下条件的索引 （）的数量：第 天的场馆与第 天的场馆不同。

现在需要考虑 个分配场景。对于第 个场景（）及其对应的问题描述如下：

• K 主席必须将 个未决定的会议分配到场馆 A， 个分配到场馆 B， 个分配到场馆 C。
• 请确定在此条件下，满足「第 天的场馆与第 天的场馆不同」的最小可能索引 的数量。

给定场馆信息和需要考量的场景，请编写程序回答这些问题。

输出 行。

在第 行（）中，输出在 K 主席将 个未决定会议分配到 A， 个分配到 B， 个分配到 C 的条件下，满足「第 天的场馆与第 天的场馆不同」的最小可能索引 的数量。

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

样例解释

样例解释

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

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

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

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

样例解释

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

样例解释

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

数据范围

• ；
• 是长度为 且由 、、 和 组成的字符串；
• 的首字符和末字符均为 ；
• ；
• （）；
• （）；
• （）；
• 等于 中 的数量（）；
• 、、、、 均为整数。

子任务

• ： 且 中 的数量不超过 ；
• ：；
• ：，；
• ：；
• ：；
• ： 不含 且所有 （）；
• ：所有 （）；
• ：无额外限制。