题目描述

有一种操作 $f$，其定义如下：

• 对于单个字符，$f(A)=T,f(T)=A,f(C)=G,f(G)=C$；
• 对于一个字符串 $s$ 和满足 $1\le i\le j\le n$ 的 $i,j$，有 $f(i,j)=f(s_j)f(s_{j-1})\dots f(s_i)$，即 $f(i,j)$ 表示用 $f(s_j),f(s_{j-1})\dots f(s_i)$ 替换 $s$ 中 $i\sim j$ 的字符。

现在给出字符串 $s$，求对于所有 $1\le i\le j\le n$ 的 $f(i,j)$，字符串操作后字典序最小的 $s$。

约束条件

• $|s|\le10^5$；
• $s$ 由 A，C，G，T 组成。

输入

输入以以下格式从标准输入给出：

$\color{#cccccc}\boxed{\color{white}{\large{|}}\color{black}s\color{white}{\large{|}}}$

输出

输出操作后字典序最小的 $s$。

样例输入

ACGTACGT

样例输出

AACGACGT