配点 : 100 点
問題文
会议 解开的人可能自然地想出了这个问题。
长度
小于或等于 N 的字符串 S 。在这里,S 中的每个字符都是 A, B, C, ? 中的任意一个,特别是 S 可以得到第 1 信和
将其重写为 N 第一个字符是 A 。
在这里,每个字符都是 A, B, C 中的某一个长度为 N 的字符串的分数,字符串的 i 信和
将其重写为 i+1 第几个字符不同的整数 i \ (1 \leq i \leq N-1) 。
Q 询问。i 查询内容如下。
非負整数 X_i, Y_i, Z_i 。在这里,X_i + Y_i + Z_i 是 您也可以写 S 可以得到第
?的数量相等。S 可以得到第?出 X_i 件 顺时针或逆时针围绕A属于Y_i 件 顺时针或逆时针围绕B属于Z_i 件 顺时针或逆时针围绕C作为可以得到的字符串得分的最大值,请输出。
制約
- N, Q, X_i, Y_i, Z_i 是一个整数
- 2 \leq N \leq 3 \times 10^5
- S 是
您也可以写
A,B,C,?组成的长度 要变为 N 的字符串 - S 可以得到第 1 信和
将其重写为 N 第一个字符是
A - 1 \leq Q \leq 2 \times 10^5
- 0 \leq X_i
- 0 \leq Y_i
- 0 \leq Z_i
- X_i + Y_i + Z_i 是
您也可以写 S 中
?的数量相等
入力
输入是按以下格式从标准输入给出的。
N S Q X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_Q Y_Q Z_Q
出力
Q 行。i 在线 i 个查询的答案。
入力例 1
9 A??B??C?A 3 1 3 1 4 1 0 0 0 5
出力例 1
8 6 4
- 1 个查询中,
ABCBABCBA如果替换为,可以得到得分 8 。 - 2 个查询中,
ABABAACAA如果替换为,可以得到得分 6 。 - 3 个查询中,
ACCBCCCCA如果替换为,可以得到得分 4 。
入力例 2
12 A???A?B????A 4 0 8 0 2 6 0 7 1 0 3 5 0
出力例 2
4 8 4 10
入力例 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
24 21 23 21 19 20 19 21 19 17 19 22 19 17 22 19 23 22 20 13 15 19 20 17 21 17