Ashmal

We process the strings in order. At step $i$, suppose we have already built some string $s$. The rules give exactly two choices:

• put $a_i$ in front, producing $a_i+s$;
• put $a_i$ in back, producing $s+a_i$.

So the greedy move is very tempting: keep the smaller of these two strings.

The main thing to prove is that this local choice does not backfire later. And yeah, for once the obvious greedy is actually right. Codeforces 800 moment, but in a nice way.

Key Observation

After some step, future strings can only be added to the beginning or the end of the entire current string.

So imagine two possible current strings $x$ and $y$ of the same length, where $x < y$. Later operations may add some big prefix $P$ in front and some suffix $Q$ at the end. The final comparison becomes:

$P + x + Q \quad \text{vs.} \quad P + y + Q$

The prefix $P$ is identical, so it cannot affect which one wins. Once comparison reaches the middle part, it compares $x$ and $y$, and since $x < y$, the first final string is still smaller.

The suffix $Q$ also does not matter, because the strings $x$ and $y$ have equal length. If they differ somewhere, the decision happens there. If they are equal, then either choice is equivalent anyway.

That means: if one current string is lexicographically smaller than another after step $i$, it will never become worse because of later operations.

Greedy Algorithm

Start with $s = \texttt{""}$.

For each string $a_i$:

1. Compute front = a_i + s.
2. Compute back = s + a_i.
3. Set $s$ to the smaller of the two.

That is it. No hidden DP goblin in the walls. The whole problem is realizing that later additions wrap both candidates in the same way, so the lexicographic order survives.

Why This Is Correct

We prove by induction that after processing the first $i$ strings, our greedy string $s$ is the lexicographically smallest string obtainable from those $i$ strings.

Base case: before processing anything, $s$ is empty, so it is trivially optimal.

Inductive step: assume after $i-1$ steps, greedy has the minimum possible string $s$. At step $i$, any valid construction must place $a_i$ either before or after some string obtainable from the first $i-1$ strings.

Because $s$ is already the smallest possible previous string, replacing any larger previous string with $s$ cannot make the result worse. Then the only remaining choice is between:

$a_i+s$

and n$s+a_i$

Greedy picks the smaller one, so it gets the best possible string after step $i$.

By induction, after all $n$ steps, greedy outputs the lexicographically smallest reachable string.

Complexity

The total length of all input strings is at most $4000$. Each step may build and compare strings of length up to the current total length, so the solution easily fits.

Time complexity: $O(L^2)$ in the simplest implementation, where $L$ is the total input length of a test case.

Memory complexity: $O(L)$.