cho.sh

DNA string

Given a DNA string S, find the shortest string over A, C, G, T that never occurs as a contiguous substring of S, breaking ties lexicographically.

Medium5StringString matchingBrute forceNo attempts yetTime limit2sMemory limit512 MB

Problem

A DNA string is a string made of the letters A, C, G, T only.

Yeongseon hired the biologist Hyobin to study human genes. The DNA that Hyobin studies is a string SS. Hyobin wants to find the shortest DNA string that never appears as a contiguous part of SS.

Several shortest answers can exist. In that case only the lexicographically smallest one counts as correct. The letters are ordered A, C, G, T.

For example, take SS = "AGGTCTA". Each of the length 1 strings A, C, G, T appears in SS, so the answer has length at least 2. Among the strings of length 2, "AA" does not appear in SS, and no string of length 2 comes before "AA" in lexicographic order, so the answer is "AA". "AG" cannot be the answer because it appears in SS, and "AAA" cannot be the answer because an answer of length 2 exists.

Given SS, write a program that finds the answer.

Input

The first line contains the string SS. SS consists of the letters A, C, G, T only, and its length is between 1 and 2,000.

Output

Print the shortest DNA string that never appears as a contiguous part of SS. If several such strings exist, print the lexicographically smallest one. The letters are ordered A, C, G, T.