409382: GYM103495 H Reverse the String

There is a string of lowercase letters, and you want to minimize its lexicographical order. What you can do is reverse an interval or do nothing.

For example, for the string abcdefg, if we reverse the interval abcdefg, it will become abfedcg.

A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:

• $$$a$$$ is a prefix of $$$b$$$, but $$$a\neq b$$$.
• In the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a letter that appears earlier in the alphabet than the corresponding letter in $$$b$$$.

The first line contains an integer $$$T$$$ ($$$1\le T \le 20$$$), denoting the number of test cases.

For the following $$$T$$$ lines, each line contains a string $$$s$$$ of lowercase letters ($$$1\le |s|\le 10^5$$$, where $$$|s|$$$ is the length of $$$s$$$).

It is guaranteed that $$$\sum |s|\le 1.5\times 10^6$$$ over all test cases.

For each test case, output the string with the minimal lexicographical order in a single line.

1
abbcabaac

aaabacbbc