B. Ашмал
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть массив $$$a$$$ из $$$n$$$ строк $$$a_{1}, a_{2}, \ldots, a_{n}$$$, каждая из которых состоит из строчных английских букв, и пустая строка $$$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}$$$.

Какую лексикографически наименьшую строку $$$s$$$ вы можете получить после $$$n$$$ шагов?

Строка $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите лексикографически наименьшую строку $$$s$$$, которую вы можете получить после $$$n$$$ шагов.

Пример
Входные данные
3
4
amir rima amin nima
1
codeforces
3
a ab abc
Выходные данные
aminamirrimanima
codeforces
aababc
Примечание

В первом наборе входных данных один из возможных способов построить лексикографически наименьшую строку $$$s$$$ выглядит следующим образом:

  1. После первого шага $$$s = \mathtt{amir}$$$, независимо от того, добавляем ли мы его в начало или в конец, так как $$$s$$$ изначально было пустым.
  2. На втором шаге мы добавляем $$$a_2 = \mathtt{rima}$$$ в конец $$$s$$$. Теперь $$$s = \mathtt{amirrima}$$$.
  3. На третьем шаге мы добавляем $$$a_3 = \mathtt{amin}$$$ в начало $$$s$$$. Теперь $$$s = \mathtt{aminamirrima}$$$.
  4. На последнем шаге мы добавляем $$$a_4 = \mathtt{nima}$$$ в конец $$$s$$$. Таким образом, окончательное значение $$$s$$$ равно $$$\mathtt{aminamirrimanima}$$$.

Можно доказать, что эта полученная строка действительно является лексикографически наименьшей строкой, которую можно получить после всех шагов.