Коротша підпослідовність

Проста

Обмеження на час виконання 1 секунда

Обмеження на використання пам'яті 128 мегабайтів

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

Знайдіть найкоротшу послідовність ДНК, яка не є підпослідовністю даної послідовності.

Вхідні дані

Один рядок містить послідовність ДНК з $n (1 \leq n \leq 1 0^{6})$ символів.

Вихідні дані

Виведіть найкоротшу послідовність ДНК, яка не є підпослідовністю даної послідовності. Якщо існує декілька можливих варіантів, виведіть будь-який з них.

Приклади

Вхідні дані #1

Відповідь #1

Відправки 385

Коефіцієнт прийняття 28%