Shortest Binary Sequence with Multiple Decompositions

Given a set of n binary strings S₁, S₂, …, Sₙ, find the shortest binary string T that can be segmented into a sequence of one or more strings from the given set in at least two distinct ways. In other words, there must exist at least two different ways to partition T such that each segment is exactly one of the given strings. If there are multiple shortest candidates, output the lexicographically smallest one.

For example, consider the following five binary strings:

S₁ = 0110, S₂ = 00, S₃ = 111, S₄ = 001100, S₅ = 110.

A valid solution is T = 001100110 which can be segmented in two ways:

• 00 + 110 + 0110 (corresponding to S₂, S₅, S₁) • 001100 + 110 (corresponding to S₄, S₅)

On the other hand, T = 0110110 is invalid because it can only be segmented uniquely as 0110 + 110 (S₁, S₅).

inputFormat

The first line contains an integer n (1 ≤ n ≤ 50) representing the number of binary strings.

The following n lines each contain a non-empty binary string (consisting only of characters '0' and '1').

outputFormat

Output the shortest binary string T meeting the condition. If multiple answers exist, output the lexicographically smallest one.

sample

5
0110
00
111
001100
110

001100110