Підпослідовності, що повторюються
Ви - мисливець за скарбами, який подорожує по світу. Нарешті, Вам потрапив до рук стародавній манускрипт, у якому вказано місце, де сховано скарб. На перший погляд текст манускрипту виглядає як беззмістовний рядок символів. Наспарвді ж місцк розміщення скарбу сховано у вигляді найбільшої повторюваної підпослідовності тексту.
Давайте уточнимо, що таке найбільша повторювана підпослідовність рядка. Розіб'ємо спочатку вхідний рядок S на дві частини F і R. Знайдемо найбільшю спільну підпослідовність L рядків F та R (найдовший рядок L, якмй є підпослідовністю F та R). Оскільки існує декілька способів розбити S на дві частини, то існує декілька можливих послідовностей L. Найбільшою повторювануваною підпослідовністю буде найдовша з них. Наприклад, найбільшою повторюваною підпослідовльністю рядка "ABCABCABAB" є "ABAB", яка отримується в результаті розбиття "ABCABCABAB" на "ABCABC" та "ABAB".
Вам потрібно знайти найбільшу повторювану підпослідовність і знайти схований скарб!
Вхідні дані
Вхідні дані складаються з декількох тестів. Кожен тест складається з одного рядка і містить до 300 великих літер. Гарантується, що кожен вхідний рядок містить як мінмум одну повторювану підпослідовність.
Останній рядок містить "#END" і не опрацьовується.
Вихідні дані
Для кожного тесту у окремому рядку потрібно вивести найбільшу повторювану підпослідовність. Якщо таких підпослідовностей існує декілька, то виведіть довільну з них.