分数: 1000 点
问题陈述
给你一个字符串 S 长度 N 由字符组成 A 和 B.
对于字符串 X 长度 N 由字符组成 1, 2,和 3, 分数 通过以下程序确定:
首先初始化变量 h_1, h_2, h_3, P to 0.
那么,对于 i = 1, 2, \dots, N 按此顺序执行以下操作:
如果 i- 第一个字符 S is
A,执行操作A;如果是的话B,执行操作 B。令 d 是由 i- 第一个字符 X.
操作A:添加 2 to h_d.
操作 B:如果 d = 2 or h_d \neq h_2,设置 P to -10^{100}。否则,添加 1 两者 h_d 和 h_2.
If h_1 = h_2 = h_3,添加 1 to P.
最终值 P 是分数。
打印一个字符串 X 最大化分数。
你有 T 测试用例解决。
约束
- 1 \leq T \leq 10^5
- 1 \leq N \leq 10^6
- S 是一个长度为的字符串 N 组成
A和B. - T 和 N 是整数。
- 总和 N 在所有测试用例中最多 10^6.
输入
输入由标准输入按以下格式给出。在这里, \mathrm{test}_i 表示 i- 第一个测试用例。
T
\mathrm{test}_1
\mathrm{test}_2
\vdots
\mathrm{test}_T
每个测试用例均按以下格式给出:
N S
输出
打印 T 行。
的 树的 i第行 (1 \leq i \leq T) 应包含一个字符串 X 最大化分数 i- 第一个测试用例。
如果有多个字符串 X 最大化分数,其中任何一个都被认为是正确的。
示例输入 1
5 4 ABBA 5 AAAAA 6 BBBBBB 7 ABABABA 20 AAABBBBBBBBAAABBBABA
示例输出 1
1333 12321 333333 1313212 33311111133121111311
让我们描述一下变化 (h_1, h_2, h_3, P) 我们继续 i = 1, 2, \dots, N.
- 对于第一个测试用例, (0,0,0,0) \rightarrow (2,0,0,0) \rightarrow (2,1,1,0) \rightarrow (2,2,2,1) \rightarrow (2,2,4,1)。最高分是 1.
- 对于第二个测试用例, (0,0,0,0) \rightarrow (2,0,0,0) \rightarrow (2,2,0,0) \rightarrow (2,2,2,1) \rightarrow (2,4,2,1) \rightarrow (4,4,2,1)。最高分是 1.
对于第三、第四和第五个测试用例,最高分数为 分别为 0, 0,和 2。可能有多个字符串 X 最大化分数,但您只需要打印其中之一。