← 返回题目列表

Codeforces · 1975/H

H. 378QAQ 和核心

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

378QAQ 有一个长度为 $$$n$$$ 的字符串 $$$s$$$。将字符串的核心定义为具有最大字典序$$$^\ddagger$$$ 顺序的子字符串$$$^\dagger$$$。

例如,“$$$\mathtt{bazoka}$$$”的核心是“$$$\mathtt{zoka}$$$”,“$$$\mathtt{aaa}$$$”的核心是“$$$\mathtt{aaa}$$$”。

378QAQ 想要重新排列字符串 $$$s$$$,以便核心按字典顺序最小。在 $$$s$$$ 的所有重新排列中找到按字典顺序排列的最小可能核心。

$$$^\dagger$$$ 字符串 $$$s$$$ 的子字符串是来自 $$$s$$$ 的连续字母段。例如,“$$$\mathtt{defor}$$$”、“$$$\mathtt{code}$$$”和“$$$\mathtt{o}$$$”都是“$$$\mathtt{codeforces}$$$”的子字符串,而“$$$\mathtt{codes}$$$”和“$$$\mathtt{aaa}$$$”是不。

$$$^\ddagger$$$ 当且仅当满足以下条件之一时,字符串 $$$p$$$ 按字典顺序小于字符串 $$$q$$$:

- $$$p$$$ 是 $$$q$$$ 的前缀,但 $$$p \ne q$$$;或
- 在 $$$p$$$ 和 $$$q$$$ 不同的第一个位置,字符串 $$$p$$$ 的元素比 $$$q$$$ 中的相应元素小(通过它们的 ASCII 代码进行比较)。

例如,“$$$\mathtt{code}$$$”和“$$$\mathtt{coda}$$$”在字典顺序上都小于“$$$\mathtt{codeforces}$$$”,而“$$$\mathtt{codeforceston}$$$”和“$$$\mathtt{z}$$$”则不然。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1\leq t\leq 10^5$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 10^6$$$) — 字符串 $$$s$$$ 的长度。

每个测试用例的下一行包含长度为 $$$n$$$ 的字符串 $$$s$$$。字符串$$$s$$$由小写英文字母组成。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出 $$$s$$$ 的所有重新排列中按字典顺序排列的最小可能核心。

示例

输入 #1

6
3
qaq
4
cccc
6
bazoka
6
zazzzz
7
ababbbb
7
ccbabcc

输出 #1

qaq
cccc
z
zzz
bbababb
cbcacbc

注意

第一个测试用例中,所有可能的重新排列及其对应的核心如下:

- “$$$\mathtt{qaq}$$$”,其核心是“$$$\mathtt{qaq}$$$”。
- “$$$\mathtt{aqq}$$$”,其核心是“$$$\mathtt{qq}$$$”。
- “$$$\mathtt{qqa}$$$”,其核心是“$$$\mathtt{qqa}$$$”。

所以所有重排方案中字典顺序最小的核心是“$$$\mathtt{qaq}$$$”。