Shortest Common Superstring

Given \(n\) strings \(S_1, S_2, \dots, S_n\), find the shortest string \(T\) such that every string \(S_i\) is a substring of \(T\). This is the well-known Shortest Common Superstring problem.

If there are multiple answers, output any one of them.

inputFormat

The first line contains an integer \(n\) indicating the number of strings. Each of the following \(n\) lines contains a non-empty string \(S_i\).

outputFormat

Output a single line containing the shortest string \(T\) that has every \(S_i\) as a substring.

sample

3
abc
bcd
cde

abcde