分数: 575 点
问题陈述
你被给予 N 字符串 S_i 由小写英文字母组成。
对于所有可能的排列 P=(P_1,P_2,\dots,P_N) of (1,2,\dots,N),记下生成的字符串如下:
- 连接 S_{P_1},S_{P_2},\dots,S_{P_N} 按此顺序。
让 A_1,A_2,\dots,A_{N!} 是序列 N! 按字典顺序排序的书面字符串。
输出 A_2.
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1 \le T \le 1.5 \times 10^5
- 2 \le N \le 3 \times 10^5
- T,N 是整数。
- S_i 是由小写英文字母组成的字符串,长度介于 1 和 10^6-1,包括在内。
- 对于单个输入,总和 N 不超过 3 \times 10^5.
- 对于单个输入,总和 |S_i| 不超过 10^6.
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N S_1 S_2 \vdots S_N
输出
输出 T 行。
的 i- 第行应包含以下问题的答案 i- 第一个测试用例。
示例输入 1
3 3 abc ac ahc 4 aaa a aaaa a 15 ks sy k ysk yks ky ksy sk syk s kys sky ys yk y
示例输出 1
abcahcac aaaaaaaaa kksksykykysskskyssyksyyksykyskyys
此输入包含三个测试用例。
对于第一个测试用例, S=( abc, ac, ahc ).
我们有 A=( abcacahc, abcahcac, acabcahc, acahcabc, ahcabcac, ahcacabc ),所以输出 A_2= abcahcac.