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;
using ll = long long;
using VI = vector<ll>;
using VB = vector<bool>;
using VD = vector<long double>;
using VC = vector<char>;
using VS = vector<string>;
using VPII = vector<pair<ll, ll> >;
using V2I = vector<VI>;
using V3I = vector<V2I>;
const ll mod{(ll)1e9 + 7};
const ll mod2{(ll)1e9 + 9};
const long double pi = 2 * acos(0.0);
const ll INF{(ll)1e14};
void godSpeed();
ll gcdExtended(ll a, ll b, ll &x, ll &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  ll x1, y1;
  ll d = gcdExtended(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return d;
}
ll modInverse(ll a, ll m = mod) {
  ll x, y;
  ll d = gcdExtended(a, m, x, y);
  if (d != 1) {
    return -1;
  }
  return (x % m + m) % mod;
}
const ll p{31LL};
ll pwr1[(ll)1e6 + 5];
ll pow1[(ll)1e6 + 5];
void preCalc(ll n, ll mod) {
  ll total{1LL};
  for (ll i{0}; i < n; ++i) {
    pow1[i] = total;
    pwr1[i] = modInverse(total, mod);
    total = total * p % mod;
  }
}
void solve() {
  string s;
  cin >> s;
  ll n{(ll)s.size()};
  preCalc(n, mod);
  ll preSum[(ll)1e6 + 5];
  ll hash_val1{};
  for (ll i{0}; i < n; ++i) {
    hash_val1 = (hash_val1 + (s[i] - 'a' + 1) * pow1[i]) % mod;
    preSum[i] = hash_val1;
  }
  VI vec;
  for (ll i{0}; i < n - 1; ++i) {
    ll tem1{(preSum[n - 1] - preSum[i] + mod) % mod};
    tem1 = tem1 * pwr1[i + 1] % mod;
    ll pr{tem1};
    if (preSum[n - 2 - i] == pr) vec.push_back({n - i - 1});
  }
  sort(vec.begin(), vec.end());
  ll st{}, en{(ll)vec.size() - 1};
  while (st <= en) {
    ll mid{(st + en) / 2}, len{vec[mid]};
    auto pr{preSum[len - 1]};
    bool find{};
    for (ll i{1}; i < n - len; i++) {
      ll val{};
      val = (preSum[i + len - 1] - preSum[i - 1] + mod) % mod;
      val = val * pwr1[i] % mod;
      if (pr == val) {
        find = 1;
        break;
      }
    }
    if (find)
      st = mid + 1;
    else
      en = mid - 1;
  }
  if (en < 0)
    cout << "Just a legend";
  else
    cout << s.substr(0, vec[en]);
}
int32_t main() {
  godSpeed();
  solve();
}
void godSpeed() {
  ios::sync_with_stdio(0);
  cin.tie(0);
}