Вы - охотник за сокровищами, путешествующий по миру. Наконец, Вам попал в руки древний манускрипт, в котором указано место где спрятан клад. С первого взгляда текст манускрипта выглядит как бессмысленная строка символов. На самом же деле место расположения клада скрыто в виде наибольшей повторяющейся подпоследовательности текста. Давайте уточним, что такое наибольшая повторяющаяся подпоследовательность строки. Разобъем сначала входную строку \textbf{S} на две части \textbf{F и} \textbf{R}. Найдем наибольшую общую подпоследовательность \textbf{L} строк \textbf{F} и \textbf{R} (самую длинную строку \textbf{L}, являющуюся подпоследовательностью \textbf{F} и \textbf{R}). Поскольку существует несколько способов разбить \textbf{S} на две части, то существует несколько возможных последовательностей \textbf{L}. Наибольшей повторяющейся подпоследовательностью является самая длинная из них. Например, наибольшая повторяющаяся подпоследовательность строки "\textbf{ABCABCABAB}" является "\textbf{ABAB}", которая получается в результате разбиения "\textbf{ABCABCABAB}" на "\textbf{ABCABC}" и "\textbf{ABAB}". Вам следует найти наибольшую повторяющуюся подпоследовательность и найти спрятанное сокровище! \InputFile Входные данные состоят из нескольких тестов. Каждый тест состоит из одной строки и содержит до \textbf{300 }заглавных букв. Гарантируется, что каждая входная строка содержит как минимум одну повторяющуюся подпоследовательность. Последняя строка содержит "\textbf{#END}" и не обрабатывается. \OutputFile Для каждого теста в отдельной строке следует вывести наибольшую повторяющуюся подпоследовательность. Если таких подпоследовательностей существует несколько, то вывести любую из них.