A16807 · Ashmal · GESP考级

题目描述

你有一个由 $n$ 个字符串 $a_1, a_2, \ldots, a_n$ 组成的数组 $a$，每个字符串均仅包含小写英文字母，并且有一个空字符串 $s$。 在第 $i$ 步（$1 \le i \le n$）时，你可以选择以下两种操作之一： - 将 $a_i$ 添加到 $s$ 的开头，或者 - 将 $a_i$ 添加到 $s$ 的末尾。 例如，如果在第 $i$ 步之前 $s = \mathtt{aba}$ 且 $a_i = \mathtt{bba}$，则第 $i$ 步后 $s$ 可能为 $\mathtt{ababba}$ 或 $\mathtt{bbaaba}$。 你需要求出在经过 $n$ 步操作后，可以得到的字典序最小的字符串 $s$。 如果两个长度相同的字符串 $a$ 和 $b$，第一个不同的位置处，$a$ 的字母比 $b$ 的字母在字母表中更靠前，则称 $a$ 的字典序小于 $b$。

每个测试点包含多组测试数据。第一行为测试用例数 $t$（$1 \le t \le 500$）。接下来的每组测试数据描述如下： 第一行为一个整数 $n$（$1 \le n \le 1000$）——数组 $a$ 的大小。第二行为 $n$ 个字符串 $a_1, a_2, \ldots, a_n$（$1 \le |a_i| \le 4000$），每个字符串由小写英文字母组成。 保证所有测试用例中 $n$ 之和不超过 $1000$，输入中所有字符串的总长度不超过 $4000$。

对于每组测试数据，输出经过 $n$ 步操作后可以得到的字典序最小的字符串 $s$。

输入 #1

3
4
amir rima amin nima
1
codeforces
3
a ab abc

输出 #1

aminamirrimanima
codeforces
aababc