← 返回题目列表

AtCoder · abc434_f

I. 连续(第二)

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

分数: 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.