Description

Given $n$ $\texttt{01}$ code strings $S_1, S_2, \dots, S_n$, your task is to find a code string $T$ such that it can be decomposed in at least two different ways as a concatenation of the $S_i$.

For example:

Given $5$ $\texttt{01}$ code strings: $S_1=\texttt{0110}, S_2=\texttt{00}, S_3=\texttt{111}, S_4=\texttt{001100}, S_5=\texttt{110}$. Then one valid code string $T$ is: \texttt{001100110}, which has the following two decompositions:

\texttt{00}+\texttt{110}+\texttt{0110} $(S_2+S_5+S_1)$ or \texttt{001100}+\texttt{110} $(S_4+S_5)$.

But 0110110 does not meet the requirement; it has only one decomposition \texttt{0110}+\texttt{110} $(S_1+S_5)$.

You must find the shortest valid code string $T$. If there are multiple shortest valid code strings $T$, output the lexicographically smallest one.

Input Format

The first line contains an integer $n$, the number of $\texttt{01}$ code strings. Each of the next $n$ lines contains one $\texttt{01}$ code string of length at most $20$.

Output Format

Output two lines. The first line is the length of the required code string $T$. The second line is the code string $T$. For all the testdata, a solution always exists.

5
0110
00
111
001100
110

9
001100110

Hint

• $n \le 20$.

Translated by ChatGPT 5