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 maxN = 1000000 + 100;
const long long SEED = 1331LL;
struct Hash {
  long long hash;
  int start;
  Hash() {}
  Hash(long long _hash, int _start) {
    hash = _hash;
    start = _start;
  }
  bool operator<(const Hash &b) const {
    return hash < b.hash || (hash == b.hash && start < b.start);
  }
};
char a[maxN];
int n;
long long v[maxN];
long long Hp[maxN], Hs[maxN];
int main() {
  scanf("%s", a);
  n = strlen(a);
  long long power = 1;
  Hp[0] = Hs[0] = 0;
  vector<int> vp;
  for (int i = 1; i <= n; i++) {
    Hp[i] = Hp[i - 1] * SEED + a[i - 1];
    Hs[i] = Hs[i - 1] + a[n - i] * power;
    power *= SEED;
    if (i < n - 1 && Hp[i] == Hs[i]) vp.push_back(i);
  }
  int best = 0, pos = 0;
  int left = 0, right = vp.size() - 1;
  while (left <= right) {
    int k = left + right >> 1;
    long long h = 0;
    long long power = 1;
    for (int i = 1; i < vp[k] + 1; i++) {
      h = h * SEED + a[i];
      if (i > 1) power *= SEED;
    }
    int size = 0;
    v[size++] = h;
    for (int j = vp[k] + 1; j < n - 1; j++) {
      h = (h - power * a[j - vp[k]]) * SEED + a[j];
      v[size++] = h;
    }
    sort(v, v + size);
    for (int i = 0; i < size; i++) {
      if (v[i] == Hp[vp[k]]) {
        best = vp[k];
        break;
      }
    }
    if (best == vp[k])
      left = k + 1;
    else
      right = k - 1;
  }
  if (best == 0)
    puts("Just a legend");
  else {
    for (int i = 0; i < best; i++) {
      printf("%c", a[i]);
    }
    printf("\n");
  }
  return 0;
}