#P18010. Max Conference

Max Conference

Max Conference

给定长度为 NN 的字符串 SS,每个字符是 A、B、C 或 ?,且首尾字符均为 A。

一个只含 A、B、C 的长度为 NN 的字符串,其得分定义为相邻字符不同的位置对数量,即满足第 ii 个字符与第 i+1i+1 个字符不同的 i∈[1,N−1]i\in[1,N-1] 的个数。

有 QQ 次相互独立的询问。每次给定非负整数 Xi,Yi,ZiX_i,Y_i,Z_i,三者之和等于 SS 中 ? 的个数。将其中恰好 XiX_i 个 ? 替换为 A、YiY_i 个替换为 B、ZiZ_i 个替换为 C,求能获得的最大得分。

输入格式

第一行一个整数 NN。第二行字符串 SS。第三行一个整数 QQ。接下来 QQ 行,每行三个整数 Xi,Yi,ZiX_i,Y_i,Z_i。

输出格式

输出 QQ 行,每行给出对应询问的最大得分。

数据范围

2≤N≤3×1052\le N\le3\times10^5,1≤Q≤2×1051\le Q\le2\times10^5,Xi,Yi,Zi≥0X_i,Y_i,Z_i\ge0,且 Xi+Yi+ZiX_i+Y_i+Z_i 等于 SS 中 ? 的个数。SS 的长度为 NN,首尾均为 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