Smallest Supersequence

Given a list of strings, your task is to find the smallest string (in terms of length) that contains each of the given strings as a subsequence. A string A is a subsequence of string B if A can be derived from B by deleting some (or none) of the characters without changing the order of the remaining characters. Formally, for strings (s) and (t), (s) is a subsequence of (t) if there exists indices (i_1 < i_2 < \cdots < i_{|s|}) such that (s[j] = t[i_j]) for all valid (j). If there are multiple answers satisfying the condition, output the lexicographically smallest one. This problem is challenging since the search space can be large and requires generating permutations in order to guarantee the minimal solution.

inputFormat

The input is given via standard input. The first line contains an integer (n) (1 (\leq n \leq 10)) indicating the number of strings. Each of the next (n) lines contains a non-empty string. It is guaranteed that the total input size is small.

outputFormat

Output via standard output the smallest supersequence string that contains every given string as a subsequence. If more than one such string is possible, output the lexicographically smallest one.## sample

3
abc
bc
ac

abc