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;
bool vis[2 * 1000996];
int idx, len;
struct State {
  int len, link;
  map<char, int> nxtc;
} SA[2 * 1000996];
int NumOcc[2 * 1000996];
char str[1000996];
vector<pair<int, int> > lenState;
class SuffixAutomata {
  int sz, last, fnl;
  void init(int idx) {
    SA[idx].len = 0, SA[idx].link = -1;
    SA[idx].nxtc.clear();
  }
  void traverse(int cur, char *ch, int l) {
    while (*ch && NumOcc[cur] >= 3 && cur < sz) {
      if (vis[cur]) len = l;
      int p = SA[cur].nxtc[*ch];
      cur = p, ++ch, ++l;
    }
  }

 public:
  SuffixAutomata() {
    sz = last = 0;
    init(0);
    lenState.clear();
    ++sz;
  }
  int size() { return sz; }
  void extend(char ch) {
    int p, q, clone, cur = sz++;
    init(cur);
    fnl = cur;
    SA[cur].len = SA[last].len + 1;
    NumOcc[cur] = 1;
    lenState.push_back(make_pair(SA[cur].len, cur));
    for (p = last; p != -1 && SA[p].nxtc.count(ch) == 0; p = SA[p].link)
      SA[p].nxtc[ch] = cur;
    if (p == -1)
      SA[cur].link = 0;
    else {
      q = SA[p].nxtc[ch];
      if (SA[p].len + 1 == SA[q].len)
        SA[cur].link = q;
      else {
        clone = sz++;
        init(clone);
        SA[clone] = SA[q];
        SA[clone].len = SA[p].len + 1;
        for (; p != -1 && SA[p].nxtc[ch] == q; p = SA[p].link)
          SA[p].nxtc[ch] = clone;
        SA[cur].link = SA[q].link = clone;
        NumOcc[clone] = 0;
        lenState.push_back(make_pair(SA[clone].len, clone));
      }
    }
    last = cur;
  }
  void traverse(char *str) { traverse(0, str, 0); }
  void numOcc() {
    int i, p, q;
    sort(lenState.begin(), lenState.end());
    for (i = lenState.size() - 1; i >= 0; --i) {
      q = lenState[i].second;
      p = SA[q].link;
      NumOcc[p] += NumOcc[q];
    }
  }
  void crawl() {
    int cur = fnl;
    memset(vis, false, sizeof(vis));
    while (cur > 0) {
      vis[cur] = true;
      cur = SA[cur].link;
    }
  }
};
int main() {
  int i;
  while (scanf("%s", str) != EOF) {
    SuffixAutomata sa;
    for (i = 0; str[i]; ++i) sa.extend(str[i]);
    sa.numOcc();
    sa.crawl();
    len = -1;
    sa.traverse(str);
    if (len <= 0)
      puts("Just a legend");
    else {
      str[len] = 0;
      puts(str);
    }
  }
  return 0;
}