P16968 [SCCPC 2026] Baldur's Leap 3

You are given a string $S$ consisting of lowercase English letters, and an initially empty string $T$. You need to perform some operations on $S$ until it becomes an empty string. Each time, you may perform one of the following three operations: - Delete the first character of $S$ and append it to the end of $T$. - Delete the last character of $S$ and append it to the end of $T$. - Choose non-empty strings $A, B$ such that $S = A B A^R$. Let $S = B$, and append the string $A$ to the end of $T$. Here, $A^R$ denotes the reverse of the string $A$. Among all possible sequences of operations, find the lexicographically smallest $T$ that can be obtained.

This problem contains multiple testdata. The first line contains a positive integer $t$ ($1 \le t \le 10^5$), denoting the number of test cases. For each test case: Input one line containing a string $S$ of lowercase letters ($1 \le |S| \le 5 \times 10^5$). It is guaranteed that the sum of $|S|$ over all test cases does not exceed $5 \times 10^5$.

For each test case, output one line containing a string representing the answer.

Translated by ChatGPT 5