Для многих задач вычислительной биологии информация, хранящаяся в молекуле ДНК, может быть представлена обычной строкой из символов A, C, G, T.

Интересно отметить, что ДНК большинства живых существ содержит большое число повторов, то есть многие подстроки встречаются в ней два и более раз. Выявление и классификация повторов является важным этапом анализа геномов.

Однако, в данной задаче повторы искать не нужно. Наоборот, вам требуется найти уникальную (то есть имеющую ровно одно вхождение) подстроку наименьшей длины.

 

Входные данные - единственная строка, содержащая от 1 до 10⁵ символов из алфавита {'A', 'C', 'G', 'T'}.

 

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

 

Примеры

Входные данные	Выходные данные
ACAAC	AA
TTTTT	TTTTT