Марсианин Василий сегодня устроился работать в одну Очень Секретную Организацию. Для выполнения дальнейших заданий Вася должен придумать свой секретный пароль для шифровки сообщений. Он ответственно подошел к делу и заранее приготовил отличное слово на марсианском языке (известно, что марсианский алфавит состоит из 10⁵ символов). Но к сожалению, новому сотруднику никто не сказал, что существует одно Очень Важное Правило: пароль не может содержать двух одинаковых подстрок (до появления этого правила ленивые агенты просто много раз повторяли свое имя, что плохо сказывалось на безопасности).

Подстрокой называется непустая часть строки, состоящая из подряд идущих символов исходной строки. Для примера, в строке «abс» имеются подстроки «a», «b», «c», «ab», «bc» и «abc». Других подстрок в строке «abc» нет.

Василий потратил очень много времени и сил, чтобы запомнить свой пароль, и совсем не хочет придумывать что-то новое. Поэтому он решил, что возьмет паролем подстроку исходного слова, которая не противоречит Очень Важному Правилу. Тогда ему не придется запоминать ничего нового. В то же время он хочет, чтобы пароль был как можно более надежным, поэтому нужна самая длинная такая подстрока. Но времени, чтобы искать ее, уже почти не осталось. Напишите программу, которая найдет такую подстроку.