Найдите это Повсюду!
Представьте, что у вас есть очень длинный текст
t. Компания хочет отыскать самую длинную подстроку s, которая удовлетворяет нескольким условиям:sявляется префиксомt
sявляется суффиксомt
sвстречается как подстрока вt
Сможете им помочь?
Входные данные
В единственной строке содержится текст
t (1 ≤ |t| ≤ ).Выходные данные
Программа должна вывести самую длинную строку
s, которая удовлетворяет всем перечисленным условиям, или вывести Impossible, если такую строку найти невозможно.Примеры
Вход | Выход |
fixfixfix | fix |
hello | Impossible |
abcabdab | ab |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB