CF2180B Ashmal

You have an array $ a $ of $ n $ strings $ a_{1}, a_{2}, \ldots, a_{n} $ , each consisting of lowercase English letters, and an empty string $ s $ . In the $ i $ -th ( $ 1 \le i \le n $ ) step, you should do one of the following: - add $ a_{i} $ to the beginning of $ s $ , or - add $ a_{i} $ to the end of $ s $ . For example, if before the $ i $ -th step $ s = \mathtt{aba} $ and $ a_{i} = \mathtt{bba} $ , after the $ i $ -th step, $ s $ will be equal to $ \mathtt{ababba} $ or $ \mathtt{bbaaba} $ . What's the lexicographically smallest string $ s $ you can reach after $ n $ steps? A string $ a $ is lexicographically smaller than a string $ b $ of the same length, if and only if the following holds: - in the first position where $ a $ and $ b $ differ, the string $ a $ has a letter that appears earlier in the alphabet than the corresponding letter in $ b $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 1000 $ ) — size of array $ a $ . The next line contains $ n $ strings $ a_{1}, a_{2}, \ldots, a_{n} $ ( $ 1 \le |a_i| \le 4000 $ ), each consisting of lowercase English letters. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 1000 $ , and the total length of all strings in the input (over all test cases) does not exceed $ 4000 $ .

For each test case, print the lexicographically minimum string $ s $ you can reach after $ n $ steps.

In the first test case, one possible way to construct the lexicographically minimum string $ s $ is as follows: 1. After the first step, $ s = \mathtt{amir} $ regardless of whether we add it to the beginning or the end, since $ s $ was initially empty. 2. In the second step, we add $ a_2 = \mathtt{rima} $ to the end of $ s $ . Now $ s = \mathtt{amirrima} $ . 3. In the third step, we add $ a_3 = \mathtt{amin} $ to the beginning of $ s $ . Now $ s = \mathtt{aminamirrima} $ . 4. In the last step, we add $ a_4 = \mathtt{nima} $ to the end of $ s $ . Therefore, the final value of $ s $ is $ \mathtt{aminamirrimanima} $ . It can be proven that this resulting string is indeed the lexicographically smallest string obtainable after all steps.