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 power(ll x, ll y, ll m = LLONG_MAX) {
  ll ans = 1LL;
  while (y) {
    if (y & 1) ans = (ans * x) % m;
    y /= 2;
    x = (x * x) % m;
  }
  return ans;
}
ll modInverse(ll a, ll m) { return power(a, m - 2, m); }
const ll p{47LL};
ll hash_fn(string &s, ll m) {
  ll hash_val{};
  ll power{1LL};
  for (char c : s) {
    hash_val = (hash_val + (c - 'a' + 1) * power) % m;
    power = power * p % m;
  }
  return hash_val;
}
ll inv1[(ll)1e6 + 5], inv2[(ll)1e6 + 5];
void preCalc(ll n) {
  ll total1{1LL};
  ll total2{1LL};
  for (ll i{0}; i < n; ++i) {
    inv1[i] = modInverse(total1, mod);
    inv2[i] = modInverse(total2, mod2);
    total1 = total1 * p % mod;
    total2 = total2 * p % mod2;
  }
}
void solve() {
  string s;
  cin >> s;
  preCalc((ll)s.size());
  VPII preSum;
  ll hash_val1{}, hash_val2{}, pow1{1LL}, pow2{1LL};
  for (char c : s) {
    hash_val1 = (hash_val1 + (c - 'a' + 1) * pow1) % mod;
    hash_val2 = (hash_val2 + (c - 'a' + 1) * pow2) % mod2;
    pow1 = pow1 * p % mod;
    pow2 = pow2 * p % mod2;
    preSum.push_back({hash_val1, hash_val2});
  }
  VI vec;
  for (ll i{0}; i < (ll)s.size() - 1; ++i) {
    ll tem1{(preSum[(ll)s.size() - 1].first - preSum[i].first + mod) % mod},
        tem2{(preSum[(ll)s.size() - 1].second - preSum[i].second + mod2) %
             mod2};
    tem1 = tem1 * inv1[i + 1] % mod;
    tem2 = tem2 * inv2[i + 1] % mod2;
    pair<ll, ll> pr{tem1, tem2};
    if (preSum[(ll)s.size() - 2 - i] == pr)
      vec.push_back({(ll)s.size() - 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 < (ll)s.size() - len; i++) {
      pair<ll, ll> val{};
      val.first = (preSum[i + len - 1].first - preSum[i - 1].first + mod) % mod;
      val.second =
          (preSum[i + len - 1].second - preSum[i - 1].second + mod2) % mod2;
      val.first = val.first * inv1[i] % mod;
      val.second = val.second * inv2[i] % mod2;
      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);
}