Substrings

Since phage ΦX174 was sequenced in 1977, the DNA of thousands of organisms has been decoded and stored in databases. Almost every genome sequenced today is read by shotgun sequencing. The method does not read whole chromosomes. It produces the sequences of many thousands of short fragments, each one tens to hundreds of nucleotides long. The ends of the fragments overlap, so aligning the overlaps and joining the fragments in the right order rebuilds the original sequence. Assembly gets harder as the genome gets larger, and assembly algorithms are a major research area in bioinformatics.

This problem is assembly cut down to its simplest form. You are given $N$ strings, all of length $L$. Find a string $S$ of length $L + N - 1$ such that every one of the $N$ given strings is a substring of $S$ and no two of them start at the same position. Because $S$ has length $L + N - 1$, a substring of length $L$ can start at exactly $N$ positions, so each input string takes one of those positions.

The input has $N$ lines, and each line holds one string of length $L$. $N$ and $L$ are not given separately. The strings use English uppercase and lowercase letters only, and uppercase and lowercase letters count as different characters. $2 \le N \le 100000$, $2 \le L \le 100000$, and $N \times L \le 5 \times 1024 \times 1024$. Every input has at least one answer.

Print the string of length $L + N - 1$ on one line. The $N$ substrings of length $L$ cut from it must equal the $N$ input strings exactly, duplicates included. If several strings satisfy the condition, print the lexicographically smallest one. Characters compare by their ASCII value, so every uppercase letter comes before every lowercase letter.