Password

题目来源

CF 126B

题目描述

给你一个字符串 $s$，由小写字母组成，你需要求出其中最长的一个子串 $p$，满足 $p$ 既是 $s$ 的前缀，又是 $s$ 的后缀，且在 $s$ 中以非前缀后缀的形式出现过。如果找不到输出 Just a legend。

输入一行一个字符串 $s$，输出一行一个字符串 $p$。

输入格式

一行一个字符串 $s$。

输出格式

输出一行一个字符串表示答案。

样例输入 1

fixprefixsuffix

样例输出 1

fix

样例输入 2

abcdabc

样例输出 2

Just a legend

数据范围

对于所有数据，保证 $1\leq |s| \leq 10^6$，字符串均由小写字母构成。