Problem: 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

Solution (in JAVA):

Solution:

import java.io.*;
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        InputReader in = new InputReader(System.in);
        PrintWriter p = new PrintWriter(System.out);
        
        String text = in.readString();
      
        int lps[] = computeFailArray(text);        
        int t  = lps[lps.length-1];
        boolean suffix[] = new boolean[text.length()];
        while(t>0){
            suffix[t] = true;
            t = lps[t-1];
        }
        boolean substring[] = new boolean[text.length()];
        for(int i=1;i<text.length()-1;i++){
            t = lps[i];
            while(t>0 && !substring[t]){
                substring[t] = true;
                t = lps[t-1];
            }
        }
        suffix[0] = true;
        substring[0] = true;
        for(int i=text.length()-1;i>=0;i--){
            if(suffix[i] && substring[i]){
                if(i!=0)
                    p.println(text.substring(0, i));
                else
                    p.println("Just a legend");
                break;
            }
        }
        p.flush();
        p.close();
    }
    public static int KMP(String text, String pattern){
        int n = text.length();
        int m = pattern.length();

        int fail[] = computeFailArray(pattern);
        int i=0;
        int j=0;
        while(i<n){
            if(text.charAt(i)==pattern.charAt(j)){          
                i++;
                j++;
                if(j==m){
                    return i-j;      
                }
            }
            else if(j>0)
                j=fail[j-1];
            else
                i++;            
        }
        return -1;
    }

    public static int[] computeFailArray(String pattern){
        int m = pattern.length();
        int fail[] = new int[m];
        fail[0] = 0;
        int j=0;
        int i=1;
        while(i<m){
            if(pattern.charAt(j)==pattern.charAt(i)){
                fail[i]=j+1;
                j++;
                i++;
            }
            else if(j>0){
                j=fail[j-1];
            }
            else
                i++;       
        }
        return fail;
    }

    static class InputReader {

		private final InputStream stream;
		private final byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}

		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}

}