← 返回题目列表

AtCoder · arc179_f

F. 都一样

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

分数: 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 最大化分数,但您只需要打印其中之一。