B. Perfect Substring
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a set of strings $$$s_1, s_2, \dots, s_n$$$ consisting of lowercase letters of the Latin alphabet. It is guaranteed that $$$n$$$ is an even number.

A string $$$t$$$ is called perfect if exactly $$$\frac{n}{2}$$$ strings from the set contain $$$t$$$ as a substring.

For example, for the set abc, acb, cab, and cba, the strings ab and cb are perfect, while the strings a, ca, and ooo are not.

Your task is to find the longest perfect substring or report that there is no such substring.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 1\,000$$$). The number $$$n$$$ is even.

The next $$$n$$$ lines contain the strings, with the $$$i$$$-th line containing the string $$$s_i$$$ ($$$1 \le |s_i| \le 5\,000$$$), consisting of lowercase letters of the Latin alphabet.

Additional input constraint: the sum of the lengths of the strings does not exceed $$$5\,000$$$.

Output

Print the longest perfect substring. If such a substring does not exist, print «No solution» (without quotes). If there are multiple possible answers, print any of them.

Examples
Input
4
abc
acb
cab
cba
Output
ab
Input
2
ccc
dd
Output
ccc
Input
4
acdd
ba
eda
aaad
Output
No solution
Input
2
xx
xx
Output
No solution