Source

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

Problem 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 Format

Each test consists of multiple testcases.

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

Output Format

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

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

Data Range

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