DNA string

Time limit2sMemory limit512 MB

Summary

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.

Level: Medium5 of 10
Topics: String, String matching, Brute force
Solved: No attempts yet

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 $S$ . Hyobin wants to find the shortest DNA string that never appears as a contiguous part of $S$ .

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 $S$ = "AGGTCTA". Each of the length 1 strings A, C, G, T appears in $S$ , so the answer has length at least 2. Among the strings of length 2, "AA" does not appear in $S$ , 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 $S$ , and "AAA" cannot be the answer because an answer of length 2 exists.

Given $S$ , write a program that finds the answer.

Input

The first line contains the string $S$ . $S$ 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 $S$ . If several such strings exist, print the lexicographically smallest one. The letters are ordered A, C, G, T.

Examples4

Example 1
Input
```
AGGTCTA
```
Expected output
```
AA
```
Example 2
Input
```
AGACGACGGAGAACGA
```
Expected output
```
T
```
Example 3
Input
```
A
```
Expected output
```
C
```
Example 4
Input
```
AAGATACACCGGCTTCGTG
```
Expected output
```
AAA
```