Problem Description

There is an operation $f$ defined as follows:

• For individual characters, $f(A)=T, f(T)=A, f(C)=G, f(G)=C$.
• For a string $s$ and $1\le i\le j\le n$, we have $f(i,j)=f(s_j)f(s_{j-1})\dots f(s_i)$, which means $f(i,j)$ represents the string obtained by replacing the characters $s_i$ to $s_j$ in $s$ with $f(s_i), f(s_{i+1}), \dots, f(s_j)$.

Given a string $s$, find the lexicographically smallest string obtained by applying the operation $f(i,j)$ for all $1\le i\le j\le n$ to $s$.

Constraints

• $|s|\le10^5$
• $s$ consists of characters A, C, G, T.

Input

The input is given in the following format from the standard input:

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

Output

Output the lexicographically smallest string obtained after applying the operations.

Sample Input

ACGTACGT

Sample Output

AACGACGT