F - Beautiful String Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1600 点

問題文

次の条件を満たす文字列を，美しい文字列ということにします．

  • どの文字も A, B, C のいずれかである．
  • どの隣接する 2 文字も相異なる．

例えば AB, BCAC は美しい文字列です．BB, CBAAC は美しい文字列ではありません．

美しい文字列 S が与えられます．あなたはこの文字列に対して，次の操作を繰り返し行うことができます：

  • 操作：S の隣接する 2 文字をスワップする．ただしスワップ後の S も美しい文字列でなくてはならない．

最終的な文字列 S としてありうる辞書順最小の文字列を求めてください．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 1\leq T\leq 10^5
  • S は美しい文字列である．
  • 1\leq |S|\leq 10^6
  • 1 個の入力に含まれるテストケースについて，それらの |S| の総和は 10^6 以下である．

入力

入力は以下の形式で標準入力から与えられます．

T
\text{case}_1
\vdots
\text{case}_T

各テストケースは以下の形式で与えられます．

S

出力

T 行出力してください．i 行目には i 番目のテストケースについて，最終的な文字列 S としてありうる辞書順最小の文字列を出力してください．

入力例 1

8
CAB
ACBCB
B
AC
BACBA
BABABA
ABCBCAC
CBABACABCBABABC

出力例 1

ABC
ABCBC
B
AC
ABABC
BABABA
ABCACBC
ABABACBCACBCBAB

1 番目，2 番目のテストケースについて，次が S を辞書順最小化する方法の一例となります．

  • CAB → ACB → ABC
  • ACBCB → CABCB → CBACB → BCACB → BCABC → BACBC → ABCBC

Score: 1600 points

Problem Statement

A string is called a beautiful string if and only if it satisfies the following conditions:

  • Every character is A, B, or C.
  • No two adjacent characters are the same.

For example, AB and BCAC are beautiful strings, while BB and CBAAC are not.

You are given a beautiful string S. On this string, you can repeatedly perform the following operation.

  • Operation: Swap two adjacent characters in S. Here, S must still be a beautiful string after the swap.

Find the lexicographically smallest string that S can become.

T test cases are given; solve each of them.

Constraints

  • 1\leq T\leq 10^5
  • S is a beautiful string.
  • 1\leq |S|\leq 10^6
  • The sum of |S| over all test cases in a single input is at most 10^6.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

S

Output

Print T lines. The i-th line should contain the lexicographically smallest string that S can become for the i-th test case.

Sample Input 1

8
CAB
ACBCB
B
AC
BACBA
BABABA
ABCBCAC
CBABACABCBABABC

Sample Output 1

ABC
ABCBC
B
AC
ABABC
BABABA
ABCACBC
ABABACBCACBCBAB

For each of the first and second test cases, here is a possible way to lexicographically minimize S:

  • CAB → ACB → ABC
  • ACBCB → CABCB → CBACB → BCACB → BCABC → BACBC → ABCBC