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:


//Paqueterias Incluidas
import java.io.*;
import java.util.ArrayList;

//Declaración de clases
//Clase B_Password_Cadenas:
//Métodos: kmp_Calculate: calcula el KMP de una cadena dada
//       : main: Método Principal
public class B_Password_Cadenas{
    static ArrayList<Integer> cad_Caracteres = new ArrayList();
    public static void kmp_Calculate(String palabra) {
        cad_Caracteres.add(0);
        for (int j=1, i=0; j<palabra.length(); j++){
            while((palabra.charAt(i) != palabra.charAt(j)) && i > 0){
              i = cad_Caracteres.get(i-1);
            }
            if(palabra.charAt(i) != palabra.charAt(j)){
              cad_Caracteres.add(j,i);
            }else{
              cad_Caracteres.add(j,++i);
            }
        }
    }
    public static void main(String[] args) {
        try {
            //Leemos la cadena de entrada
            boolean comparar = true;
            int longitud;
            InputStreamReader isr = new InputStreamReader(System.in);
            BufferedReader buffer = new BufferedReader(isr);
            String palabra = buffer.readLine();
            int tamPalabra = palabra.length()-1;

            //Calculamos su KMP
            kmp_Calculate(palabra);

            //Obtenemos la longitud de la palabra
            longitud = cad_Caracteres.get(tamPalabra);
            if(longitud != 0){
                for(int i=1;i<=2;i++){
                    for(int j=1; j<tamPalabra; j++){
                        if (longitud == cad_Caracteres.get(j)) {
                            comparar = false;
                            break;
                        }
                    }
                    if(comparar == true){
                        longitud = cad_Caracteres.get(longitud-1);
                        if(longitud == 0){
                            break;
                        }
                    }else{
                      break;
                    }
                }
            }
            //Impimimos que solo es una leyenda
            if(longitud == 0 || comparar == true){
                System.out.printf("Just a legend\r\n");
            //Imprimimos la contraseña
            }else{
                System.out.printf("%s\r\n",palabra.substring(0, longitud));
            }
        } catch (IOException e){
            System.out.println(e.getMessage());
        }
    }
}