← 返回题目列表

AtCoder · utpc2025_m

M. 最大会议

中文机器翻译题面 查看原题

配点 : 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