Пожалуйста, подпишитесь на официальный канал Codeforces в Telegram по ссылке https://t.me/codeforces_official. ×

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

Вам дан набор строк $$$s_1, s_2, \dots, s_n$$$, состоящих из строчных букв латинского алфавита. Гарантируется, что $$$n$$$ — чётное число.

Скажем, что строка $$$t$$$ идеальная, если ровно $$$\frac{n}{2}$$$ строк из набора содержат $$$t$$$ в качестве подстроки. Например, для набора abc, acb, cab и cba строки ab и cb являются идеальными, а строки a, ca, ooo — нет.

Ваша задача — найти самую длинную идеальную строку для заданного набора или сообщить, что такой не существует.

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 1\,000$$$). Число $$$n$$$ — чётное.

Далее следуют $$$n$$$ строк, $$$i$$$-я из них содержит строку $$$s_i$$$, состоящую из строчных букв латинского алфавита. Сумма длин строк в наборе не превосходит $$$5\,000$$$.

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

В единственной строке выведите самую длинную идеальную строку. Если такой строки не существует, выведите "No solution" (без кавычек). Если возможных ответов несколько, выведите любой из них.

Примеры
Входные данные
4
abc
acb
cab
cba
Выходные данные
ab
Входные данные
2
ccc
dd
Выходные данные
ccc
Входные данные
4
acdd
ba
eda
aaad
Выходные данные
No solution
Входные данные
2
xx
xx
Выходные данные
No solution