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 p = 31;
vector<long long> inv_p_powers;
long long power(long long a, long long b) {
  if (b == 0) return 1;
  long long temp = power(a, b / 2);
  temp = temp * temp % 1000000007;
  if (b % 2 == 1) {
    temp = temp * a % 1000000007;
  }
  return temp;
}
long long find_hash(vector<long long> &prefix_hash, int i, int j) {
  if (i == 0) return prefix_hash[j];
  long long sub_s_hash =
      (prefix_hash[j] - prefix_hash[i - 1] + 1000000007) % 1000000007;
  sub_s_hash = sub_s_hash * inv_p_powers[i] % 1000000007;
  return sub_s_hash;
}
bool check(string t, int l, vector<long long> &prefix_hash) {
  int start = 1;
  int end = start + l - 1;
  int maxi = prefix_hash.size() - 1;
  while (1) {
    if (end >= maxi) break;
    long long sub_s_hash = find_hash(prefix_hash, start, end);
    if (sub_s_hash == prefix_hash[l - 1]) return true;
    start++;
    end = start + l - 1;
  }
  return false;
}
int main() {
  int i;
  long long p_pow = 1;
  for (i = 1; i <= 1000010; i++) {
    inv_p_powers.push_back(power(p_pow, 1000000007 - 2));
    ;
    p_pow = p_pow * p % 1000000007;
  }
  string t;
  cin >> t;
  int len = t.length();
  vector<long long> prefix_hash;
  vector<long long> suffix_hash;
  long long hash = 0;
  p_pow = 1;
  for (i = 0; i <= len - 1; i++) {
    hash = (hash + p_pow * ((long long)(t[i] - 'a' + 1))) % 1000000007;
    prefix_hash.push_back(hash);
    ;
    p_pow = p_pow * p % 1000000007;
  }
  for (i = 0; i <= len - 1; i++) {
    suffix_hash.push_back(find_hash(prefix_hash, len - 1 - i, len - 1));
    ;
  }
  vector<int> ans_len;
  for (i = 0; i <= len - 1; i++) {
    if (prefix_hash[i] == suffix_hash[i]) {
      ans_len.push_back(i + 1);
      ;
    }
  }
  int high = ans_len.size() - 1;
  int low = 0;
  while (low < high) {
    int mid = (low + high + 1) / 2;
    if (check(t, ans_len[mid], prefix_hash)) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  if (check(t, ans_len[low], prefix_hash)) {
    cout << t.substr(0, ans_len[low]);
  } else
    cout << "Just a legend";
  return 0;
}