Invisible Integer

Problem Description

In the game Invisible Integer, you are given n hints. Each hint is a sequence of distinct natural numbers chosen from the set \(S = \{1,2,\dots,9\}\). Each hint is generated from a target sequence \(T\) (which is a sequence containing only digits 1 to 9 and may repeat) by the following process:

1. Randomly choose a starting position in \(T\).
2. Randomly choose a direction, either left or right.
3. Traverse from the starting position in that direction, and record each digit when it appears for the first time.

The recorded list of digits forms the hint. Note that since the hint records only the first occurrence when traversing, the hint itself does not contain any repeated digit.

Your task is: given n hints, find the shortest possible target sequence \(T\) (a sequence consisting solely of digits 1 to 9) such that for every hint there exists a contiguous segment of \(T\) whose deduplication (i.e. retaining only the first appearance of each digit in that segment) is exactly equal to the hint.

Observation: A sufficient condition for the hint to appear is that \(T\) contains the hint as a contiguous substring. (Since every hint has all distinct digits, if it appears as a contiguous substring then the deduplication of that substring is itself.)

Thus, the problem reduces to the classic Shortest Common Superstring problem: given n strings (the hints), each over the alphabet \(\{1,2,\dots,9\}\) with no repeated characters, find the shortest string \(T\) that contains every hint as a substring.

Input Format: The target sequence you output must contain each hint as a substring. The target sequence should be the one with the minimal possible length (if there are several answers, any one is accepted).

inputFormat

The input begins with an integer n (1 ≤ n ≤ 10) in the first line, indicating the number of hints. The following n lines each contain a hint. Each hint is a nonempty string composed of digits (from '1' to '9') with no repeated characters.

outputFormat

Output the shortest possible target sequence T (a string of digits) that contains every given hint as a contiguous substring. If there are multiple answers, output any one.

sample

2
12
23

123