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.*;
import java.math.*;

public class P126B {

  final long HASH_P = 31L;

  @SuppressWarnings("unchecked")
  public void run() throws Exception {
    String s = nextLine();

    int n = s.length();
    long [] hash = new long [n];
    long [] prefHash = new long [n];
    long [] suffHash = new long [n];

    long hashP = 0;
    long hashS = 0;
    long h = 1;
    for (int i = 0; i < n; i++) {
      hashP = hashP * HASH_P + s.charAt(i);
      hashS = hashS + s.charAt(n - i - 1) * h;
      prefHash[i] = hashP;
      suffHash[i] = hashS;
      hash[i] = h;
      h *= HASH_P;
    }
//System.out.println(Arrays.toString(prefHash));
//System.out.println(Arrays.toString(suffHash));

    for (int l = n - 2; l >= 1; l--) {
      if (prefHash[l - 1] == suffHash[l - 1]) {
        for (int i = 1; i <= n - l - 1; i++) {
//System.out.println(l + "\t" + i);
//System.out.println(prefHash[l - 1] + "\t" + (prefHash[i + l - 1] - prefHash[i - 1] * hash[l]));
          if (prefHash[l - 1] == prefHash[i + l - 1] - prefHash[i - 1] * hash[l]) {
//System.out.println(l + "\t" + i);
            println(s.substring(0, l));
            return;
          }
        }
      }
    }

    println("Just a legend");
  }

  public static void main(String... args) throws Exception {
    br = new BufferedReader(new InputStreamReader(System.in));
    pw = new PrintWriter(new BufferedOutputStream(System.out));
    new P126B().run();
    br.close();
    pw.close();
  }

  static BufferedReader br;
  static PrintWriter pw;
  StringTokenizer stok;

  String nextToken() throws IOException {
    while (stok == null || !stok.hasMoreTokens()) {
      String s = br.readLine();
      if (s == null) {
        return null;
      }
      stok = new StringTokenizer(s);
    }
    return stok.nextToken();
  }

  void print(byte b) {
    print("" + b);
  }

  void print(int i) {
    print("" + i);
  }

  void print(long l) {
    print("" + l);
  }

  void print(double d) {
    print("" + d);
  }

  void print(char c) {
    print("" + c);
  }

  void print(Object o) {
    if (o instanceof int[]) {
      print(Arrays.toString((int [])o));
    } else if (o instanceof long[]) {
      print(Arrays.toString((long [])o));
    } else if (o instanceof char[]) {
      print(Arrays.toString((char [])o));
    } else if (o instanceof byte[]) {
      print(Arrays.toString((byte [])o));
    } else if (o instanceof short[]) {
      print(Arrays.toString((short [])o));
    } else if (o instanceof boolean[]) {
      print(Arrays.toString((boolean [])o));
    } else if (o instanceof float[]) {
      print(Arrays.toString((float [])o));
    } else if (o instanceof double[]) {
      print(Arrays.toString((double [])o));
    } else if (o instanceof Object[]) {
      print(Arrays.toString((Object [])o));
    } else {
      println("" + o);
    }
  }

  void print(String s) {
    pw.print(s);
  }

  void println(byte b) {
    println("" + b);
  }

  void println(int i) {
    println("" + i);
  }

  void println(long l) {
    println("" + l);
  }

  void println(double d) {
    println("" + d);
  }

  void println(char c) {
    println("" + c);
  }

  void println(Object o) {
    print(o);
    println("");
  }

  void println(String s) {
    pw.println(s);
  }

  int nextInt() throws IOException {
    return Integer.parseInt(nextToken());
  }

  long nextLong() throws IOException {
    return Long.parseLong(nextToken());
  }

  double nextDouble() throws IOException {
    return Double.parseDouble(nextToken());
  }

  char nextChar() throws IOException {
    return (char) (br.read());
  }

  String next() throws IOException {
    return nextToken();
  }

  String nextLine() throws IOException {
    return br.readLine();
  }

  int [] readInt(int size) throws IOException {
    int [] array = new int [size];
    for (int i = 0; i < size; i++) {
      array[i] = nextInt();
    }
    return array;
  }

  long [] readLong(int size) throws IOException {
    long [] array = new long [size];
    for (int i = 0; i < size; i++) {
      array[i] = nextLong();
    }
    return array;
  }

  double [] readDouble(int size) throws IOException {
    double [] array = new double [size];
    for (int i = 0; i < size; i++) {
      array[i] = nextDouble();
    }
    return array;
  }

}