Problem: Legend has it that, after being defeated in Waterloo, Napoleon Bonaparte, in retrospect of his days of glory, talked to himself "Able was I ere I saw Elba." Although, it is quite doubtful that he should have said this in English, this phrase is widely known as a typical palindrome.

A palindrome is a symmetric character sequence that looks the same when read backwards, right to left. In the above Napoleon's grumble, white spaces appear at the same positions when read backwards. This is not a required condition for a palindrome. The following, ignoring spaces and punctuation marks, are known as the first conversation and the first palindromes by human beings.


"Madam, I'm Adam."
"Eve."
(by Mark Twain)


Write a program that finds palindromes in input lines.



Input

A multi-line text is given as the input. The input ends at the end of the file.

There are at most 100 lines in the input. Each line has less than 1,024 Roman alphabet characters.

Output

Corresponding to each input line, a line consisting of all the character sequences that are palindromes in the input line should be output. However, trivial palindromes consisting of only one or two characters should not be reported.

On finding palindromes, any characters in the input except Roman alphabets, such as punctuation characters, digits, space, and tabs, should be ignored. Characters that differ only in their cases should be looked upon as the same character. Whether or not the character sequences represent a proper English word or sentence does not matter.

Palindromes should be reported all in uppercase characters. When two or more palindromes are reported, they should be separated by a space character. You may report palindromes in any order.

If two or more occurrences of the same palindromes are found in the same input line, report only once. When a palindrome overlaps with another, even when one is completely included in the other, both should be reported. However, palindromes appearing in the center of another palindrome, whether or not they also appear elsewhere, should not be reported. For example, for an input line of "AAAAAA", two palindromes "AAAAAA" and "AAAAA" should be output, but not "AAAA" nor "AAA". For "AABCAAAAAA", the output remains the same.

One line should be output corresponding to one input line. If an input line does not contain any palindromes, an empty line should be output.

Example

Input

As the first man said to the
first woman:
"Madam, I'm Adam."
She responded:
"Eve."


Output

TOT

MADAMIMADAM MADAM
ERE DED
EVE

Solution (in CPP):

Solution:
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
#include <assert.h>
  
using namespace std;
  
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P> PP;
  
static const double EPS = 1e-8;

class Compare{
private:
  const int len;
  const int n;
  const int* rank;
public:
  Compare(int _l,int _n,int* _r) :
    len(_l),n(_n),rank(_r) {}
  bool operator() (int i,int j) const{
    return compare_sa(i,j,len);
  }

  bool compare_sa(int i,int j,int len) const{
    if(rank[i] != rank[j]) return rank[i] < rank[j];
    else{
      int ri = (i + len <= n ? rank[i + len] : -1);
      int rj = (j + len <= n ? rank[j + len] : -1);
      return ri < rj;
    }
  }
  
  bool equal_sa(int i,int j,int len) const{
    int ri = (i + len <= n ? rank[i + len] : -1);
    int rj = (j + len <= n ? rank[j + len] : -1);
    
    return (rank[i] == rank[j] && ri == rj);
  }
};

class SuffixArray {
protected:
  string S;
  int* rank;
  int* sa;
  int* lcp;
  int n;
private:
  void construct_sa(){
    for(int i= 0; i <= n;i++){
      sa[i] = i;
      rank[i] = (i < n ? S[i] : -1);
    }

    int* tmp = new int[2 * n + 1]();
    Compare init(1,n,rank);
    sort(sa,sa+n+1,init);

    for(int len = 1; len <= n; len *= 2){
      Compare comp(len,n,rank);
      sort(sa,sa+n+1,comp);
      
      tmp[sa[0]] = 0;
      for(int i=1;i<= n;i++){
        tmp[sa[i]] = tmp[sa[i-1]] + (comp.compare_sa(sa[i-1],sa[i],len) ? 1 : 0);
      }
      for(int i=0;i<=n;i++){
        rank[i] = tmp[i];
      }
    }
    delete[] tmp;
  }

  void construct_lcp(){
    int h = 0;
    lcp[0] = 0;

    for(int i=0;i < n;i++){
      int j= sa[rank[i] - 1];
      if(h > 0) h--;
      for(; j + h < n && i + h < n; h++){
        if(S[j + h] == '$' || S[i + h] == '$') break;
        if(S[j + h] != S[i + h]) break;
      }
      lcp[rank[i] - 1] = h;
    }
  }
  
public:
  SuffixArray(const string& _S){
    S = _S;
    n = S.length();
    rank = new int[n + 12](); //not to be too small
    sa = new int[n + 12]();
    lcp = new int[n + 12]();
    construct_sa();
    construct_lcp();
  }

  ~SuffixArray(){
    delete[] rank;
    delete[] sa;
    delete[] lcp;
  }

  int bsearch_first(const string& T){
    int lower = -1;
    int upper = S.length() + 1;
    while(lower + 1 < upper){
      int mid = lower + (upper - lower) / 2;
      if(S.compare(sa[mid],T.length(),T) < 0){
        lower = mid;
      }
      else{
        upper = mid;
      }
    }
    if(upper < 0 || S.compare(sa[upper],T.length(),T) != 0) return -1;
    return upper;
  }

  int bsearch_last(const string& T){
    int lower = -1;
    int upper = S.length() + 1;
    while(lower + 1 < upper){
      int mid = lower + (upper - lower) / 2;
      if(S.compare(sa[mid],T.length(),T) <= 0){
        lower = mid;
      }
      else{
        upper = mid;
      }
    }

    if(lower < 0 || S.compare(sa[lower],T.length(),T) != 0) return -1;
    return lower;
  }
  int hits(const string& T){
    int first = bsearch_first(T);
    int last = bsearch_last(T);

    if(first == -1 || last == -1) return 0;

    disp();
    return last - first + 1;
  }

  int get_lcp(int i) const{
    assert(i < n);
    return lcp[i];
  }

  int get_sa(int i) const{
    assert(i < n);
    return sa[i];
  }

  int get_rank(int i) const{
    assert(i < n);
    return rank[i];
  }

  int size() const{
    return n;
  }

  //for debug
  void disp() const{
    for(int i=0;i<=S.length();i++){
      printf("rank[%02d] := %02d",sa[i], rank[sa[i]]);
      printf(" lcp[%02d] := %02d ",i, lcp[i]);
      cout << S.substr(sa[i],S.length()) << endl;
    }
  }

};

class SegmentTree {
private:
  int* dat;
  int n;
public:
  SegmentTree(int _size){
    n = 1;
    while(n < _size) n *= 2;
    dat = new int[n * 2 - 1];
    fill(dat,dat + n * 2 - 1,INF);
  }

  ~SegmentTree(){
    delete[] dat;
  }

  void update(int idx,int val){
    idx += n - 1; //offset: n - 1 
    dat[idx] = val;
    while(idx > 0){
      idx = (idx - 1) / 2;
      dat[idx] = min(dat[idx * 2 + 1],dat[idx * 2 + 2]);
    }
  }

  int query(int a,int b,int idx = 0,
            int l = 0,int r = INF){
    if(r == INF) r = n;

    if(r <= a || b <= l) return INF;
    
    if(a <= l && r <= b) return dat[idx];
    
    else{
      int vl = query(a, b, idx * 2 + 1, l, (l + r) / 2);
      int vr = query(a, b, idx * 2 + 2, (l + r) / 2, r);
      return min(vl,vr);
    }
  }
};

bool comp(const string& s1,const string& s2){
  return s1.size() > s2.size();
}

int main(){
  string input;
  while(getline(cin,input)){
    
    string str;
    for(int i=0;i<input.size();i++){
      if(isalpha(input[i])){
        str.push_back(toupper(input[i]));
      }
    }

    string r_str = str;
    reverse(r_str.begin(),r_str.end());
    SuffixArray sa(str + "$" + r_str);
    SegmentTree segtree(sa.size());

    for(int i=0; i < sa.size(); i++){
      segtree.update(i,sa.get_lcp(i));
    }

    set<string> visited;
    vector<string> palindromes;

    //odd
    for(int center=0;center<str.size();center++){
      int r_center = sa.size() - center - 1;
      int lcp = segtree.query(
        min(
          sa.get_rank(center),
          sa.get_rank(r_center)
        ),
        max(
          sa.get_rank(center),
          sa.get_rank(r_center)
        )
      );

      if(lcp == INF) continue;
      if(lcp <= 1) continue;

      string tmp = str.substr(center-lcp + 1,2 * lcp - 1);
      if(visited.count(tmp)) continue;

      visited.insert(tmp);
      palindromes.push_back(tmp);
    }

    //even
    for(int center_rhs=1;center_rhs<str.size();center_rhs++){
      int center_lhs = center_rhs - 1;
      int r_center_lhs = sa.size() - center_lhs - 1;
      int lcp = segtree.query(
        min(
          sa.get_rank(center_rhs),
          sa.get_rank(r_center_lhs)
        ),
        max(
          sa.get_rank(center_rhs),
          sa.get_rank(r_center_lhs)
        )
      );

      if(lcp == INF) continue;
      if(lcp <= 1) continue;

      string tmp = str.substr(center_lhs - lcp + 1,lcp * 2);
      if(visited.count(tmp)) continue;
      visited.insert(tmp);
      palindromes.push_back(tmp);
    }


    sort(palindromes.begin(),palindromes.end(),comp);
    visited.clear();
    
    bool is_first = true;
    for(int i = 0; i < palindromes.size();i++){
      if(visited.count(palindromes[i])) continue;
      
      printf("%s%s",is_first ? "" : " ",palindromes[i].c_str());
      is_first = false;

      if(palindromes[i].size() % 2 == 0){
        for(int len = 2,offset=0; len <= palindromes[i].size(); len += 2,offset++){
          string tmp = palindromes[i].substr(palindromes[i].size()/2 - 1 - offset,len);
          visited.insert(tmp);
        }
      }
      else if(palindromes[i].size() % 2 == 1){
        for(int len = 3,offset=0; len <= palindromes[i].size(); len += 2,offset++){
          string tmp = palindromes[i].substr(palindromes[i].size()/2 - 1 - offset,len);
          visited.insert(tmp);
        }
      }
    }

    printf("\n");
  }
}