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 long long N = 1e6 + 5, mod = 1e9 + 7, base = 31, base2 = 37;
char s[N];
long long pw[N], pw2[N], inv[N], inv2[N], n;
long long power(long long x, long long y) {
  x %= mod;
  long long ret = 1;
  while (y) {
    if (y & 1) ret = (ret * x) % mod;
    y /= 2;
    x = (x * x) % mod;
  }
  return ret;
}
void pre() {
  pw[0] = pw2[0] = inv[0] = inv2[0] = 1;
  long long baseInv = power(base, mod - 2);
  long long baseInv2 = power(base2, mod - 2);
  for (int i = 1; i < N; i++) {
    pw[i] = (pw[i - 1] * base) % mod;
    pw2[i] = (pw2[i - 1] * base2) % mod;
    inv[i] = (inv[i - 1] * baseInv) % mod;
    inv2[i] = (inv2[i - 1] * baseInv2) % mod;
  }
}
bool checkHash(long long cHash, long long cHash2, long long k) {
  long long hash = 0, hash2 = 0, sz = 0;
  for (int i = 1; i < n - 1; i++) {
    hash = (hash + ((s[i] - 'a' + 1) * pw[sz])) % mod;
    hash2 = (hash2 + ((s[i] - 'a' + 1) * pw2[sz])) % mod;
    if (sz == k - 1) {
      if (hash == cHash and hash2 == cHash2) return 1;
      hash = ((hash + mod - (s[i - k + 1] - 'a' + 1)) * inv[1]) % mod;
      hash2 = ((hash2 + mod - (s[i - k + 1] - 'a' + 1)) * inv2[1]) % mod;
    }
    sz++;
    sz = min(k - 1, sz);
  }
  return 0;
}
vector<pair<int, pair<long long, long long> > > hashes;
int main() {
  pre();
  gets(s);
  n = strlen(s);
  long long lHash1 = 0, lHash2 = 0, rHash1 = 0, rHash2 = 0, l = 0, r = n - 1,
            c = 0;
  while (l < n - 1 and r > 0) {
    rHash1 = ((rHash1 * pw[1] + (s[r] - 'a' + 1)) + mod) % mod;
    rHash2 = ((rHash2 * pw2[1] + (s[r] - 'a' + 1)) + mod) % mod;
    lHash1 = ((lHash1 + ((s[l] - 'a' + 1) * pw[c])) + mod) % mod;
    lHash2 = ((lHash2 + ((s[l] - 'a' + 1) * pw2[c])) + mod) % mod;
    c++, l++, r--;
    if (lHash1 == rHash1 and lHash2 == rHash2)
      hashes.push_back({c, {lHash1, lHash2}});
  }
  int st = 0, en = hashes.size() - 1, mid, ans = 0;
  while (st <= en) {
    mid = (st + en) / 2;
    if (checkHash(hashes[mid].second.first, hashes[mid].second.second,
                  hashes[mid].first)) {
      ans = hashes[mid].first;
      st = mid + 1;
    } else
      en = mid - 1;
  }
  for (int i = 0; i < ans; i++) printf("%c", s[i]);
  puts(ans ? "" : "Just a legend");
  return 0;
}