Унікальні заходи#10732
Емілі втомилася від навчання вдома протягом усього 2020 року. Вона помітила, що одні й ті ж завдання повторюються знову і знову: їй потрібно готувати їжу та мити посуд. Потім настає час її занять; після цього вона знову миє посуд, відвідує ще одне заняття, миє ще кілька тарілок перед приготуванням їжі і востаннє за день миє посуд.
Проте є частина її дня, яку вона обожнює: це коли послідовність дій, які вона виконує, трапляється лише один раз протягом дня. Найбільше вона радіє, коли ця послідовність унікальна і дуже коротка.
Кожна дія позначається великою літерою. Знаючи список справ, які Емілі має виконати сьогодні, допоможіть їй знайти найкращий момент її дня: знайдіть найкоротший підрядок, що зустрічається у вхідних даних лише один раз.
Якщо "Приготування їжі" позначено як , "Миття посуду" як , а "Навчання" як , то список занять у наведеному прикладі — це C D S D S D C D, а найкоротший підрядок, що зустрічається лише один раз — це (усі однобуквені підрядки та інші двобуквені підрядки зустрічаються щонайменше двічі).
Один рядок, що містить послідовність з n~(0 < n \le 300000) великих літер (від 'A' до 'Z').
Виведіть один рядок з найкоротшим підрядком, який зустрічається на вході лише один раз. Якщо існує декілька найкоротших підрядків (однієї довжини), виведіть той, який зустрічається першим.
Приклад 1