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. \InputFile One line contains a DNA sequence with $n~(1 \le n \le 10^6)$ characters. \OutputFile 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.