Home

Contest: Task: Related: TaskD TaskF

Score : $800$ points

Problem Statement

Given is a string $S$ consisting of a and b. Find the lexicographically greatest string that can be obtained by applying the following operation to $S$ zero or more times:

  • Choose two characters of $S$ that are the same letter. Reverse the string between them and delete the chosen two characters. In other words: let $s_i$ denote the $i$-th character of $S$. Choose $i < j$ such that $s_i = s_j$ and replace $S$ with $s_1\dots s_{i-1}s_{j-1}\dots s_{i+1}s_{j+1}\dots s_{|S|}$.

In this problem, you are given $T$ test cases. The $i$-th test case is represented as $S_i$ and asks you to solve the problem above for $S = S_i$.

Constraints

  • $1 \leq T \leq 2\times 10^5$
  • $1 \leq |S_i|\quad (i=1,\dots, T)$
  • $1 \leq |S_1| + \dots + |S_T| \leq 2\times 10^5$
  • $S_i$ consists of a and b.

Input

Input is given from Standard Input in the following format:

$T$
$S_1$
$\vdots$
$S_T$

Output

Print $T$ lines. The $i$-th line should contain the lexicographically greatest string that can be obtained by applying the operation to $S_i$ zero or more times.

Sample Input 1

20
abbaa
babbb
aabbabaa
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbabaaaaabbaababaaabbabbbbbaaaaa
babbbaaaabaababbbabaabaaaaababaa
bbaababababbbaaabaabababaabbabab
abaabbabaabaaaaabaaaabbaabaaaaab
aabababbabbabbabbaaaabbabbbabaab
aabababbabbbbaaaabbaaaaabbaaaabb
abbbbaabaaabababaaaababababbaabb
aaaaaaaaaaaaaaaaaaaaaaabbbbbbbbb
aaaaaaaaaabbbbbbbbbbbbbbbbbbbbbb
abababaaababaaabbbbbaaaaaaabbbbb
aabbaaaaababaabbbbbbbbbaabaaabbb
babababbababbbababbbbbababbbabbb
bbbbababbababbbabababbabbabbbbbb
aaaaaaaaaaaaaaaaababababbbabbbbb
aabababbabbabababababababbbbabbb

Sample Output 1

bba
bba
bbba
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbaaaaaaaa
bbbbbbbbbbbbbaaaaaaa
bbbbbbbbbbbbbbbb
bbbbbbbbbb
bbbbbbbbbbbbbbbbab
bbbbbbbbbbbbbb
bbbbbbbbbbbbbabb
abbbbbbbbb
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbaaaaaaaaa
bbbbbbbbbbbbbbbaaaaa
bbbbbbbbbbbbbbbbbbbbbb
bbbbbbbbbbbbbbbbbbbbba
bbbbbbbbbaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbba
  • In the $1$-st test case, we can do the operation for the $1$-st and $4$-th characters to make $S$ bba.
  • In the $2$-nd test case, we can do the operation for the $1$-st and $5$-th characters to make $S$ bba.
  • In the $3$-rd test case, we can do the operation for the $1$-st and $2$-nd characters to make $S$ bbabaa, then do it for the $3$-rd and $5$-th characters to make $S$ bbba.