human
Asterix, Obelix and their temporary buddies Suffix and Prefix has finally found the Harmony temple. However, its doors were firmly locked and even Obelix had no luck opening them.

A little later they found a string s, carved on a rock below the temple's gates. Asterix supposed that that's the password that opens the temple and read the string aloud. However, nothing happened. Then Asterix supposed that a password is some substring t of the string s.

Prefix supposed that the substring t is the beginning of the string s.
Suffix supposed that the substring t should be the end of the string s.
and Obelix supposed that t should be located somewhere inside the string s, that is, t is neither its beginning, nor its end.

Asterix chose the substring t so as to please all his companions. Besides, from all acceptable variants Asterix chose the longest one (as Asterix loves long strings). When Asterix read the substring t aloud, the temple doors opened. 

You know the string s. Find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend.

Input

You are given the string s whose length can vary from 1 to 106 (inclusive), consisting of small Latin letters.

Output

Print the string t. If a suitable t string does not exist, then print "Just a legend" without the quotes.

Examples

Input

fixprefixsuffix

Output

fix

Input

abcdabc

Output

Just a legend
Using python3 can you solve the prior task?

Can you provide a Python program to find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend?
assistant
#Here is Python program to find the substring t or determine that such substring does not exist and all that's been written above is just a nice legend.

# -*- coding:utf-8 -*-

"""

created by shuangquan.huang at 12/25/19

"""

import collections
import time
import os
import sys
import bisect
import heapq
from typing import List
from functools import lru_cache

# TLE at the 91th test case, 97 cases in total
def solve_hash(s):
    MOD = 10**9+7
    N = len(s)
    ha, hb = 0, 0
    possible = []
    x, oa = 1, ord('a')
    w = [ord(v)-oa for v in s]
    for i, v in enumerate(w):
        ha = (ha * 26 + v) % MOD
        hb = (w[N-i-1] * x + hb) % MOD
        x = (x * 26) % MOD
        if ha == hb:
            possible.append((i+1))
    
    def check(m):
        l = possible[m]
        t = s.find(s[:l], 1)
        return t > 0 and t != N-l
    
    lo, hi = 0, len(possible)
    while lo <= hi:
        m = (lo + hi) // 2
        if check(m):
            lo = m + 1
        else:
            hi = m - 1
    
    return s[:possible[hi]] if hi >= 0 else 'Just a legend'
    
    
def solve_zscore(s):
    """
    https://cp-algorithms.com/string/z-function.html
    
    In z-function, z[i] means from i, the maximum number of chars is prefix of s.
    when i + z[i] == len(s), mean s[i:] == s[:z[i]], if there is another index j < i and z[j] >= z[i] means s[:z[i]]
    are prefix, suffix and another substring
    
    """
    z, maxl = [0] * len(s), 0
    i, l, r, n = 1, 0, 0, len(s)
    while i < n:
        if i <= r:
            z[i] = min(r-i+1, z[i-l])
        
        while i + z[i] < n and s[z[i]] == s[z[i] + i]:
            z[i] += 1
        
        if i + z[i] - 1 > r:
            l, r = i, i + z[i] - 1
        
        if i + z[i] == n:
            if z[i] <= maxl:
                return s[:z[i]]
        maxl = max(maxl, z[i])
        i += 1
        
    return 'Just a legend'

def solve_prefix(s):
    """
    https://cp-algorithms.com/string/prefix-function.html
    The prefix function for this string is defined as an array π of length n,
    where π[i] is the length of the longest proper prefix of the substring s[0…i]
    which is also a suffix of this...