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;
long long modOfNegative(long long x, long long m) {
  long long xVal = ((llabs(x / m) + 1) * m) * (-1);
  return llabs(x - xVal);
}
long long pow2(long long a, long long b, long long MOD2) {
  long long x = 1, y = a;
  while (b > 0) {
    if (b % 2 == 1) {
      x = (x * y);
      if (x > MOD2) x %= MOD2;
    }
    y = (y * y);
    if (y > MOD2) y %= MOD2;
    b /= 2;
  }
  return x;
}
long long modInverse(long long a, long long m) { return pow2(a, m - 2, m); }
char sArr[1000006];
string storeS[2];
long long storeHash[2];
vector<long long> vecHash[2];
const long long base = 29;
const long long hashMod = 1009010791;
long long modInvCal[1000006];
void genModInv() {
  long long x = modInverse(base, hashMod);
  modInvCal[1] = x;
  modInvCal[0] = 1;
  for (int i = 2; i < 1000006; i++) {
    modInvCal[i] = (modInvCal[i - 1] * x) % hashMod;
  }
}
long long basePow[1000006];
void genPow() {
  basePow[0] = 1;
  for (int i = 1; i < 1000006; i++) {
    basePow[i] = (basePow[i - 1] * base) % hashMod;
  }
}
long long hashing(int ith, int len) {
  long long hashVal = 0;
  for (int i = 0; i < len; i++) {
    long long x = sArr[i] - 97 + 1;
    hashVal *= base;
    hashVal %= hashMod;
    hashVal += x;
    hashVal %= hashMod;
    vecHash[ith].push_back(hashVal);
  }
  return hashVal;
}
long long getHashStartingAt(int iPos, long long mainHash, int len,
                            int ithString) {
  if (iPos == 0) return mainHash;
  if (iPos == len) return 0;
  long long curHash = mainHash;
  curHash =
      curHash - (vecHash[ithString][iPos - 1] * basePow[len - iPos]) % hashMod;
  if (curHash < 0)
    curHash = modOfNegative(curHash, hashMod);
  else
    curHash %= hashMod;
  return curHash;
}
long long getHashOfSubString(int i, int j, long long mainHash, int len,
                             int ithString) {
  long long curHash = getHashStartingAt(i, mainHash, len, ithString);
  curHash = curHash - getHashStartingAt(j + 1, mainHash, len, ithString);
  if (curHash < 0)
    curHash = modOfNegative(curHash, hashMod);
  else
    curHash %= hashMod;
  curHash = (curHash * modInvCal[len - 1 - j]) % hashMod;
  curHash %= hashMod;
  return curHash;
}
string str;
vector<int> v;
int pi[1000006];
void KMP() {
  int it = 0;
  pi[0] = 0;
  int len = str.length();
  for (int i = 1; i < len; i++) {
    if (str[it] == str[i]) {
      it++;
      pi[i] = it;
    } else if (it) {
      it = pi[it - 1];
      i--;
    } else
      pi[i] = 0;
  }
  for (int i = len - 2; i > 0; i--) v.push_back(pi[i]);
}
int main() {
  genModInv();
  genPow();
  cin >> str;
  KMP();
  int len = str.length();
  for (int i = 0; i < len; i++) sArr[i] = str[i];
  storeS[0] = str;
  storeHash[0] = hashing(0, len);
  sort(v.begin(), v.end());
  bool paisi = false;
  for (int i = v.size() - 1; i >= 0; i--) {
    int id = v[i];
    if (id == 0) continue;
    if (i != 0 && id == v[i - 1]) continue;
    int st = 0;
    int ed = id - 1;
    long long hashP = getHashOfSubString(st, ed, storeHash[0], len, 0);
    st = len - id;
    ed = len - 1;
    long long hashS = getHashOfSubString(st, ed, storeHash[0], len, 0);
    if (hashP == hashS) {
      for (int i = 0; i < id; i++) cout << str[i];
      cout << "\n";
      paisi = true;
      break;
    }
  }
  if (!paisi)
    cout << "Just a legend"
         << "\n";
  return 0;
}