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;
template <typename T>
inline bool read(T& x) {
  x = 0;
  char c = getchar();
  int f = 1;
  while (!isdigit(c) && (c != '-') && (c != EOF)) c = getchar();
  if (c == EOF) return 0;
  if (c == '-') f = -1, c = getchar();
  while (isdigit(c)) {
    x = (x << 1) + (x << 3) + (c & 15);
    c = getchar();
  }
  x *= f;
  return 1;
}
template <typename T, typename... Args>
inline bool read(T& x, Args&... args) {
  bool res = 1;
  res &= read(x);
  res &= read(args...);
  return res;
}
const int M = 1000000007, INF = 0x3f3f3f3f;
const long long INFLL = 0x3f3f3f3f3f3f3f3fLL;
const int N = 1000010;
const double EPS = 1e-6;
inline bool isc(char c) { return (c >= 'a') && (c <= 'z'); }
inline int reads(char* s) {
  int len = 0;
  char c = getchar();
  while (c != EOF && (!isc(c))) c = getchar();
  if (c == EOF) return 0;
  while (c != EOF && isc(c)) (*(++s)) = c, ++len, c = getchar();
  (*(++s)) = '\0';
  return len;
}
char s[N];
int n, nex[N], pos[N];
inline void init() {
  n = reads(s);
  int j = 0;
  for (int i = (2), (ii) = (n); i <= (ii); ++i) {
    while (j && (s[j + 1] != s[i])) j = nex[j];
    if (s[j + 1] == s[i]) ++j;
    ++pos[j];
    nex[i] = j;
  }
}
inline void solve() {
  int res = nex[n];
  --pos[res];
  while ((res) && (!pos[res])) res = nex[res];
  if (res == 0) {
    puts("Just a legend");
  } else {
    s[res + 1] = '\0';
    printf("%s\n", s + 1);
  }
}
signed main() {
  init();
  solve();
  return 0;
}