БерНефтьГазАлмазБанк имеет филиалы в n городах, причем n четно. Руководство банка хочет издать календарь с названиями всех этих городов, записанными в два столбца: календарь должен состоять из n / 2 строк одинаковой длины, каждая из которых содержит ровно два названия и ровно один разделитель между ними. При этом название каждого города нужно использовать в календаре ровно один раз. По историческим причинам в качестве разделителя слов в календаре используется символ d.
Руководство БерНефтьГазАлмазБанка хочет показать, что для него одинаково важны все филиалы, поэтому порядок их следования в календаре должен быть беспрестрастным: если «склеить» все n / 2 строк словаря в одну так, чтобы между двумя словами из одной строки были разделители, а между разными строками календаря разделителей не было, получается лексикографически наименьшая возможная строка. Это равносильно тому, что нужно найти лексикографически наименьший календарь, причем сравнение календарей происходит построчно.
Помогите БерНефтьГазАлмазБанку — составьте искомый календарь.
Выходные данные
Выведите n / 2 строк одинаковой длины — искомый календарь. Каждая строка должна содержать ровно 2 слова и ровно 1 разделитель между ними. Если решений несколько, выведите лексикографически минимальное. Лексикографическое сравнение строк реализует оператор < в современных языках программирования.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
b
aa
hg
c
.
|
aa.b
c.hg
|
|
2
|
2
aa
a
!
|
a!aa
|
|
3
|
2
aa
a
|
|
aa|a
|