Code Submission Evaluation System Login

CSES Problem Set

Subsequence


Task | Statistics


CSES - Subsequence

Time limit:1.00 s Memory limit:512 MB

You are given a DNA sequence that consists 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 can print any of them.

Constraints
Example

Input:
ACGTACGT

Output:
AAA