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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int MN = 1e6 + 44;
const int mod = 1e9 + 9, b = 444555;
long long rcshnt[MN];
int n;
char a[MN];
bool check(int len) {
  ;
  long long curr = 0;
  for (int i = 0; i < len; ++i) curr = (curr * b + a[i]) % mod;
  long long pre = curr;
  ;
  for (int i = len; i < n - 1; ++i) {
    ;
    ;
    curr = ((curr - a[i - len] * rcshnt[len - 1]) % mod * b + a[i]) % mod;
    ;
    if ((pre - curr) % mod == 0) {
      ;
      return true;
    }
  };
  return false;
}
int main() {
  scanf("%s", a);
  n = strlen(a);
  rcshnt[0] = 1;
  for (int i = 1; i < MN; ++i) {
    rcshnt[i] = rcshnt[i - 1] * b % mod;
  }
  for (int i = 0; i < 10; ++i)
    ;
  vector<int> pre;
  long long ph = 0, sh = 0;
  for (int i = 0; i < n - 1; ++i) {
    ph = (ph * b + a[i]) % mod;
    sh = (sh + a[n - i - 1] * rcshnt[i]) % mod;
    if (ph == sh) {
      pre.push_back(i + 1);
      ;
    }
  }
  int low = 1, high = n - 1, ans = 0;
  while (low <= high) {
    int med = (low + high) / 2;
    if (check(med)) {
      ans = med;
      low = med + 1;
    } else
      high = med - 1;
  }
  int res = -1;
  for (auto c : pre) {
    if (c <= ans) res = max(res, c);
  }
  if (res <= 0) {
    printf("Just a legend\n");
  } else {
    a[res] = 0;
    printf("%s\n", a);
  }
}