← 返回题目列表

AtCoder · arc113_e

E. Rvom 和 Rsrev

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

分数: 800 点

问题陈述

给定的是一个字符串 S 组成 a 和 b。按字典顺序查找 最大 字符串,可通过以下操作获得 S 零次或多次:

  • 选择两个字符 S 是相同的字母。反转它们之间的字符串并删除所选的两个字符。换句话说:让 s_i 表示 i- 第一个字符 S。选择 i < j 这样 s_i = s_j 并替换 S 与 s_1\dots s_{i-1}s_{j-1}\dots s_{i+1}s_{j+1}\dots s_{|S|}.

在这个问题中,给你 T 测试用例。的 i第一个测试用例表示为 S_i 并请您解决上述问题 S = S_i.

约束

  • 1 \leq T \leq 2\times 10^5
  • 1 \leq |S_i|\quad (i=1,\dots, T)
  • 1 \leq |S_1| + \dots + |S_T| \leq 2\times 10^5
  • S_i 包括 a 和 b.

输入

输入由标准输入按以下格式给出:

T
S_1
\vdots
S_T

输出

打印 T 行。的 i- 第行应包含按字典顺序排列的最大字符串,该字符串可通过将操作应用于 S_i 零次或多次。


示例输入 1

20
abbaa
babbb
aabbabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbabaaaaabbaababaaabbabbbbbaaaaa
babbbaaaabaababbbabaabaaaaababaa
bbaababababbbaaabaabababaabbabab
abaabbabaabaaaaabaaaabbaabaaaaab
aabababbabbabbabbaaaabbabbbabaab
aabababbabbbbaaaabbaaaaabbaaaabb
abbbbaabaaabababaaaababababbaabb
aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb
aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb
abababaaababaaabbbbbaaaaaaabbbbb
aabbaaaaababaabbbbbbbbbaabaaabbb
babababbababbbababbbbbababbbabbb
bbbbababbababbbabababbabbabbbbbb
aaaaaaaaaaaaaaaaababababbbabbbbb
aabababbabbabababababababbbbabbb

示例输出 1

bba
bba
bbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbaaaaaaaa
bbbbbbbbbbbbbaaaaaaa
bbbbbbbbbbbbbbbb
bbbbbbbbbb
bbbbbbbbbbbbbbbbab
bbbbbbbbbbbbbb
bbbbbbbbbbbbbabb
abbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbaaaaaaaaa
bbbbbbbbbbbbbbbaaaaa
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbba
  • 在 1-st 测试用例,我们可以执行以下操作 1-st 和 4要制作的第个字符 S bba.
  • 在 2-nd测试用例,我们可以执行以下操作 1-st 和 5要制作的第个字符 S bba.
  • 在 3-rd 测试用例,我们可以执行以下操作 1-st 和 2-要制作的第一个字符 S bbabaa,然后为 3-rd 和 5要制作的第个字符 S bbba.