#P18010. Max Conference
Max Conference
Max Conference
给定长度为 的字符串 ,每个字符是 A、B、C 或 ?,且首尾字符均为 A。
一个只含 A、B、C 的长度为 的字符串,其得分定义为相邻字符不同的位置对数量,即满足第 个字符与第 个字符不同的 的个数。
有 次相互独立的询问。每次给定非负整数 ,三者之和等于 中 ? 的个数。将其中恰好 个 ? 替换为 A、 个替换为 B、 个替换为 C,求能获得的最大得分。
输入格式
第一行一个整数 。第二行字符串 。第三行一个整数 。接下来 行,每行三个整数 。
输出格式
输出 行,每行给出对应询问的最大得分。
数据范围
,,,且 等于 中 ? 的个数。 的长度为 ,首尾均为 A。
样例 1
输入
9
A??B??C?A
3
1 3 1
4 1 0
0 0 5
输出
8
6
4
样例 2
输入
12
A???A?B????A
4
0 8 0
2 6 0
7 1 0
3 5 0
输出
4
8
4
10