你有一个由 $$$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$$$。
示例
输入复制
3
4
amir rima amin nima
1
codeforces
3
a ab abc
输出复制
aminamirrimanima
codeforces
aababc
注意
在第一个测试用例中,构造按字典顺序排列的最小字符串 $$$s$$$ 的一种可能方法如下:
- 第一步之后,$$$s = \mathtt{amir}$$$ 无论我们将其添加到开头还是末尾,因为 $$$s$$$ 最初是空的。
- 在第二步中,我们将 $$$a_2 = \mathtt{rima}$$$ 添加到 $$$s$$$ 的末尾。现在$$$s = \mathtt{amirrima}$$$。
- 在第三步中,我们将 $$$a_3 = \mathtt{amin}$$$ 添加到 $$$s$$$ 的开头。现在$$$s = \mathtt{aminamirrima}$$$。
- 在最后一步中,我们将 $$$a_4 = \mathtt{nima}$$$ 添加到 $$$s$$$ 的末尾。因此,$$$s$$$的最终值为$$$\mathtt{aminamirrimanima}$$$。
可以证明,这个结果字符串确实是经过所有步骤后可获得的按字典顺序最小的字符串。