Password

Problem Source

CF 126B

Problem Description

You are given a string $s$ consisting of lowercase letters. Find the longest substring $p$ such that $p$ is both a prefix and a suffix of $s$, and appears somewhere in $s$ as a substring that is neither a prefix nor a suffix. If no such substring exists, output Just a legend.

Given a string $s$, output a string $p$.

Input Format

One line containing a string $s$.

Output Format

Output one line containing a string: the answer.

Sample Input 1

fixprefixsuffix

Sample Output 1

fix

Sample Input 2

abcdabc

Sample Output 2

Just a legend

Constraints

For all data, $1 \leq |s| \leq 10^6$, and the string consists of lowercase letters only.