CSES - Shortest Subsequence
  • Time limit: 1.00 s
  • Memory limit: 512 MB
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

The only input line contains a DNA sequence with $n$ 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.

Constraints
  • $1 \le n \le 10^6$
Example

Input:
ACGTACGT

Output:
AAA