P9348 A Lonely Walk on a Fragrant Garden Path

Wandering along a quiet, deep path, you pick up fragments of memory and put them into two long pockets. After collecting them all and pouring them out, what kind of story will they form?

There are two strings $S,T$. Initially, $S$ is given and $T$ is the empty string. Each time, you may perform one of the following three operations until $S$ becomes the empty string: 1. Delete the first character of $S$, and insert this character at the beginning of $T$. 1. Delete the first character of $S$, and insert this character at the end of $T$. 1. Delete the last character of $S$, and insert this character at the beginning of $T$. a3 wants to know, after $S$ becomes the empty string, the lexicographically smallest $T$ that can be formed.

**This problem contains multiple test cases.** The first line contains an integer $Q$, which denotes the number of test cases. For each test case, one line contains a string $S$.

For each test case, output one line containing a string, which is the lexicographically smallest $T$ that can be formed.

**[Sample 1 Explanation]** - For $\texttt{ababdca}$, perform operations of type $1,2,1,2,2,2,1$ in order, and you can obtain $\texttt{aaabbdc}$. - For $\texttt{dcbcadb}$, perform operations of type $1,1,1,2,3,1,2$ in order, and you can obtain $\texttt{abbcdcd}$. **[Constraints and Agreements]** **This problem uses bundled testdata.** - Subtask 1 (5 points): $S$ consists of at most two distinct characters. - Subtask 2 (10 points): $\sum |S|\le 12$. - Subtask 3 (15 points): $\sum |S|\le 100$. - Subtask 4 (25 points): $\sum |S|\le 3\times 10^3$. - Subtask 5 (20 points): $\sum |S|\le 2\times 10^5$. - Subtask 6 (25 points): no special restrictions. For $100\%$ of the data, $1\le Q\le 3\times 10^5$, $1\le |S|\le 10^6$, $1\le \sum |S|\le 2\times 10^6$, and $S$ consists only of lowercase letters. Translated by ChatGPT 5