Кратчайшая подпоследовательность

Вам задана последовательность ДНК, состоящая из символов $A,C,G$ и $T$.

Найдите кратчайшую последовательность ДНК, которая не является подпоследовательностью исходной последовательности.

Входные данные

Одна строка содержит последовательность ДНК с $n(1\le n\le 10^6)$ символами.

Выходные данные

Выведите самую короткую последовательность ДНК, не являющуюся подпоследовательностью исходной последовательности. Если решений несколько, то выведите любое из них.

Примеры