AT_abc434_f.[ABC434F] Concat (2nd)

给定 $N$ 个仅由小写英文字母组成的字符串 $S_i$。

对 $ (1,2, \dots, N) $ 的所有排列 $P=(P_1, P_2, \dots, P_N)$，按顺序写下 $S_{P_1}, S_{P_2}, \dots, S_{P_N}$ 拼接后的字符串。

将得到的 $N!$ 个字符串按字典序从小到大排序，记为 $A_1, A_2, \dots, A_{N!}$。请输出 $A_2$。

输入包含 $T$ 组测试用例，要求对每组测试用例进行求解。

输入通过标准输入给出，格式如下：

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

每组测试用例的格式如下：

$N$
$S_1$
$S_2$
$\vdots$
$S_N$

输出共 $T$ 行。

第 $i$ 行输出第 $i$ 组测试用例的答案。

样例解释 1

本输入包含三组测试。

对于第一组，$S = ($abc, ac, ahc$)$。
得到的所有拼接排列为 $A = ($abcacahc, abcahcac, acabcahc, acahcabc, ahcabcac, ahcacabc$)$，因此输出 $A_2 = $ abcahcac。

数据范围

• $1 \leq T \leq 1.5 \times 10^5$
• $2 \leq N \leq 3 \times 10^5$
• $T, N$ 均为整数。
• $S_i$ 是仅包含小写英文字母的字符串，长度满足 $1 \leq |S_i| \leq 10^6-1$。
• 对于一组输入，所有 $N$ 的和不超过 $3 \times 10^5$。
• 对于一组输入，所有字符串长度的总和不超过 $10^6$。

由 ChatGPT 5 翻译