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 翻译