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;
std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6 + 5;
int Mod[2] = {1000000007, 1000000009};
int Base[2] = {37, 43};
int mod1[] = {1000000007, 1000000009, 1000000021, 1000000033, 1000000087};
int mod2[] = {1000000093, 1000000097, 1000000103, 1000000123, 1000000181};
int base1[] = {23, 29, 31, 37, 41};
int base2[] = {43, 47, 53, 59, 61, 67};
char s[N];
long long Pow[N][2];
long long HashF[N][2], HashR[N][2];
int len;
inline void build_hash() {
  len = strlen(s);
  HashF[0][0] = 0, HashR[len + 1][0] = 0;
  HashF[0][1] = 0, HashR[len + 1][1] = 0;
  for (int i = 1; i <= len; i++) {
    HashF[i][0] = (HashF[i - 1][0] * Base[0] + s[i - 1]) % Mod[0];
    HashR[len - i + 1][0] =
        (HashR[len - i + 2][0] * Base[0] + s[len - i]) % Mod[0];
    HashF[i][1] = (HashF[i - 1][1] * Base[1] + s[i - 1]) % Mod[1];
    HashR[len - i + 1][1] =
        (HashR[len - i + 2][1] * Base[1] + s[len - i]) % Mod[1];
  }
}
inline long long get_hash(char *st) {
  long long Hash1 = 0, Hash2 = 0;
  int l = strlen(st);
  for (int i = 1; i <= l; i++) {
    Hash1 = (Hash1 * Base[0] + st[i - 1]) % Mod[0], Hash1 %= Mod[0];
    Hash2 = (Hash2 * Base[1] + st[i - 1]) % Mod[1], Hash2 %= Mod[1];
  }
  return (Hash1 << 31) | Hash2;
}
inline long long get_fhash(int l, int r) {
  l++, r++;
  if (l == 1) return (HashF[r][0] << 31) | HashF[r][1];
  long long Hash1 =
      (HashF[r][0] - HashF[l - 1][0] * Pow[r - l + 1][0] % Mod[0]);
  Hash1 = (Hash1 + Mod[0]) % Mod[0];
  long long Hash2 =
      (HashF[r][1] - HashF[l - 1][1] * Pow[r - l + 1][1] % Mod[1]);
  Hash2 = (Hash2 + Mod[1]) % Mod[1];
  return (Hash1 << 31) | Hash2;
}
inline long long get_rhash(int l, int r) {
  l++, r++;
  if (r == len) return (HashR[l][0] << 31) | HashR[l][1];
  long long Hash1 =
      (HashR[l][0] - HashR[r + 1][0] * Pow[r - l + 1][0] % Mod[0]);
  Hash1 = (Hash1 + Mod[0]) % Mod[0];
  long long Hash2 =
      (HashR[l][1] - HashR[r + 1][1] * Pow[r - l + 1][1] % Mod[1]);
  Hash2 = (Hash2 + Mod[1]) % Mod[1];
  return (Hash1 << 31) | Hash2;
}
inline void gen_pow() {
  shuffle(mod1, mod1 + 5, rng), shuffle(mod2, mod2 + 5, rng);
  shuffle(base1, base1 + 5, rng), shuffle(base2, base2 + 5, rng);
  Mod[0] = mod1[rng() % ((4) - (0) + 1) + (0)],
  Mod[1] = mod2[rng() % ((4) - (0) + 1) + (0)];
  Base[0] = base1[rng() % ((4) - (0) + 1) + (0)],
  Base[1] = base2[rng() % ((4) - (0) + 1) + (0)];
  Pow[0][0] = Pow[0][1] = 1;
  for (int i = 1; i < N; i++) {
    Pow[i][0] = Pow[i - 1][0] * Base[0] % Mod[0];
    Pow[i][1] = Pow[i - 1][1] * Base[1] % Mod[1];
  }
}
vector<int> Length;
bool ok(int l) {
  for (int i = 1; i + Length[l] - 1 < len - 1; i++) {
    if (get_fhash(i, i + Length[l] - 1) == get_fhash(0, Length[l] - 1))
      return true;
  }
  return false;
}
int main(int argc, char const *argv[]) {
  gen_pow();
  cerr << Mod[0] << " " << Mod[1] << " " << Base[0] << " " << Base[1] << endl;
  scanf("%s", s);
  build_hash();
  for (int i = 0; i < len - 1; i++) {
    if (get_fhash(0, i) == get_fhash(len - 1 - i, len - 1)) {
      Length.push_back(i + 1);
    }
  }
  if (!(int)Length.size()) return printf("Just a legend\n"), 0;
  int lo = 0, hi = Length.size() - 1, mx = -1;
  while (lo <= hi) {
    int mid = (lo + hi) >> 1;
    if (ok(mid)) {
      mx = mid;
      lo = mid + 1;
    } else
      hi = mid - 1;
  }
  if (mx == -1) return printf("Just a legend\n"), 0;
  for (int i = 0; i < Length[mx]; i++) printf("%c", s[i]);
  return 0;
}