409382: GYM103495 H Reverse the String

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Reverse the Stringtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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$$$.
Input

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.

Output

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

ExampleInput
1
abbcabaac
Output
aaabacbbc

加入题单

上一题 下一题 算法标签: