题目描述

给定一个仅由小写英文字母组成的字符串 $s$。请找出一个最长的字符串 $t$，使它同时满足以下条件：

• $t$ 是 $s$ 的前缀；
• $t$ 是 $s$ 的后缀；
• $t$ 还在 $s$ 的内部出现过至少一次。这里的“内部出现”指该次出现既不从 $s$ 的第一个字符开始，也不在 $s$ 的最后一个字符结束。

若有多个满足条件的字符串，输出其中长度最大的一个。

例如，若某次出现与前缀或后缀有重叠，只要它本身既不是整串的前缀，也不是整串的后缀，仍然可以作为内部出现。

输入格式

输入一行字符串 $s$。

$s$ 仅由小写英文字母组成，且 $1 \le |s| \le 10^6$。

输出格式

若存在满足条件的字符串 $t$，输出 $t$。

否则输出 Just a legend。

样例

样例 1

输入：

fixprefixsuffix

输出：

fix

样例 2

输入：

abcdabc

输出：

Just a legend