Shortest Subsequence

You are given a DNA sequence consisting of characters $A,C,G$ and $T$.

Your task is to find the shortest DNA sequence that is not a subsequence of the original sequence.

Input

One line contains a DNA sequence with $n(1\le n\le 10^6)$ characters.

Output

Print the shortest DNA sequence that is not a subsequence of the original sequence. If there are several solutions, you may print any of them.

Examples