版权声明

本题版权归 Long Long OJ 所有。

题目描述

有一种变换 $f$，其定义如下：$f(\tt{A})\to\tt{T},$$f(\tt{C})\to\tt{G},$$f(\tt{G})\to\tt{C},$$f(\tt{T})\to\tt{A}$。

给定一个只含 $\tt{ACGT}$ 的字符串 $S$，请确定 $S$ 在进行操作后可能出现的最小字典序：

• 选出 $S$ 的一个非空子串 $T$。
• 给 $T$ 中的每个字符施加一次变换 $f$。
• 翻转子串 $T$。

输入格式

本题有多组数据。

对于每组数据，输入一行一个只含 $\tt{ACGT}$ 的字符串 $S$。

输出格式

对于每组数据，输出一行一个字符串，表示 $S$ 在操作后可能出现的最小字典序。

样例

ACGTACGT
ACACACAC

AACGACGT
ACACACAG

提示

样例解释：

对于第 $1$ 组数据，最优解在选出 $S$ 的第 $2$ 至 $4$ 个字符（$\tt{A\color{red}{CGT}\color{black}ACGT}$）时取到。

对于第 $2$ 组数据，最优解在选出 $S$ 的最后一个字符（$\tt{ACACACA\color{red}{C}}$）时取到。

本题共 $5$ 个测试点，每个测试点 $20$ 分：

1. $S$ 在样例输入中出现过。
2. $|S|=1$。
3. $|S| \le 8$。
4. $S$ 中的每个字符都相同。
5. 无特殊限制。

对于 $100\%$ 的数据，$1 \le |S| \le 10^5$。

保证单个测试点内所有数据中 $|S|$ 的和不超过 $10^6$。