Source

This problem is adapted from Long Long OJ. All rights reserved.

Description

There is a transfrom $f$ defined as follows: $f(\tt{A})\to\tt{T},$$f(\tt{C})\to\tt{G},$$f(\tt{G})\to\tt{C},$$f(\tt{T})\to\tt{A}.$

Given a string $S$ consisting of characters $\tt{ACGT}$, find the lexicographically smallest string that can be obtained after applying the following operations:

• Choose a non-empty substring of $S$ (let's call it $T$).
• Perfrom the transfrom $f$ once for each character in the substring $T$.
• Reverse the substring $T$.

Input

Each test consists of multiple testcases.

For each testcase, you should input a string $S$ consisting of characters $\tt{ACGT}$.

Output

For each testcase, you should output a string representing the lexicographically smallest string that can be obtained after applying the operations above.

Samples

ACGTACGT
ACACACAC

AACGACGT
ACACACAG

Tips

Sample Explanation:

In the first testcase, It's best to choose the second to fourth characters ($\tt{A\color{red}{CGT}\color{black}ACGT}$) of $S$.

In the second testcase, It's best to choose the last character ($\tt{ACACACA\color{red}{C}}$) of $S$.

There are $5$ tests, each of which is worth $20$ points:

1. $S$ appeared in the sample input.
2. $|S|=1.$
3. $|S| \le 8.$
4. All the characters in the string $S$ are the same.
5. No additional constraints.

For $100\%$ of the testcases, $1 \le |S| \le 10^5.$

It is guaranteed that the sum of $|S|$ over all the testcases in one test does not exceed $10^6$.