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:


//package practice;
import java.util.*;
import java.io.*;


public class Practice {
    
   
    
   
    public static void main(String args[])
    { 
      InputReader in=new InputReader(System.in);
      String str=in.next();
      int n=str.length();
      int pre[]=new int[n];
      if(n==1)
          System.out.println("Just a legend");
      else if(n==2)
          System.out.println("Just a legend");
      else if(n==3)
      {
          if(str.charAt(0)==str.charAt(1)&&str.charAt(0)==str.charAt(2))
              System.out.println(str.charAt(0));
          else
              System.out.println("Just a legend");
              
      }
      
      else
      {
        pre[0]=0;
        int index=0;
        for(int i=1;i<n;i++)
        {
           if(str.charAt(i)==str.charAt(index))
           {
               pre[i]=pre[i-1]+1;
               index++;
              
           }
           else
           {
              
              while(index!=0)
              {   
                 
                  index=pre[index-1];
                  
                  if(str.charAt(i)==str.charAt(index)){
                      pre[i]=index+1;
                      index++;
                      break;
                  }
                 
               }
            
           }             
      }
        
     
      if(pre[n-1]==0)
          System.out.println("Just a legend");
      else
      {
          boolean found=false;
          for(int i=0;i<n-2;i++)
          {
              if(pre[i]==pre[n-1]){
                  System.out.println(str.substring(0,pre[i]));
                  
                  found=true;
                  break;
              }
              
          }
          if(!found)
          {
              if(pre[pre[n-1]-1]>0)
                  System.out.println(str.substring(0,pre[pre[n-1]-1]));
              else
                  System.out.println("Just a legend");
          }
      }
                
    }}
    
    
    
 static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
 
        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
 
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            
 
            return buf[curChar++];
        }
 
        public int nextInt() {
            int c = read();
 
            while (isSpaceChar(c))
                c = read();
 
            int sgn = 1;
 
            if (c == '-') {
                sgn = -1;
                c = read();
            }
 
            int res = 0;
 
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
 
                res *= 10;
                res += c & 15;
 
                c = read();
            } while (!isSpaceChar(c));
 
            return res * sgn;
        }
 
        public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
 
            for (int i = 0; i < arraySize; i++)
                array[i] = nextInt();
 
            return array;
        }
 
        public long nextLong() {
            int c = read();
 
            while (isSpaceChar(c))
                c = read();
 
            int sign = 1;
 
            if (c == '-') {
                sign = -1;
 
                c = read();
            }
 
            long result = 0;
 
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
 
                result *= 10;
                result += c & 15;
 
                c = read();
            } while (!isSpaceChar(c));
 
            return result * sign;
        }
 
        public long[] nextLongArray(int arraySize) {
            long array[] = new long[arraySize];
 
            for (int i = 0; i < arraySize; i++)
                array[i] = nextLong();
 
            return array;
        }
 
        public float nextFloat() // problematic
        {
            float result, div;
            byte c;
 
            result = 0;
            div = 1;
            c = (byte) read();
 
            while (c <= ' ')
                c = (byte) read();
 
            boolean isNegative = (c == '-');
 
            if (isNegative)
                c = (byte) read();
 
            do {
                result = result * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');
 
            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    result += (c - '0') / (div *= 10);
 
            if (isNegative)
                return -result;
 
            return result;
        }
 
        public double nextDouble() // not completely accurate
        {
            double ret = 0, div = 1;
            byte c = (byte) read();
 
            while (c <= ' ')
                c = (byte) read();
 
            boolean neg = (c == '-');
 
            if (neg)
                c = (byte) read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = (byte) read()) >= '0' && c <= '9');
 
            if (c == '.')
                while ((c = (byte) read()) >= '0' && c <= '9')
                    ret += (c - '0') / (div *= 10);
 
            if (neg)
                return -ret;
 
            return ret;
        }
 
        public String next() {
            int c = read();
 
            while (isSpaceChar(c))
                c = read();
 
            StringBuilder res = new StringBuilder();
 
            do {
                res.appendCodePoint(c);
 
                c = read();
            } while (!isSpaceChar(c));
 
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        public String nextLine() {
            int c = read();
 
            StringBuilder result = new StringBuilder();
 
            do {
                result.appendCodePoint(c);
 
                c = read();
            } while (!isNewLine(c));
 
            return result.toString();
        }
 
        public boolean isNewLine(int c) {
            return c == '\n';
        }
 
        public void close() {
            try {
                stream.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
 
    }
    
}