Problem: Given a string s, determine if it contains any palindrome of length exactly 100 as a subsequence. If it has any, print any one of them. If it doesn't have any, print a palindrome that is a subsequence of s and is as long as possible.

Input

The only line of the input contains one string s of length n (1 ≤ n ≤ 5·104) containing only lowercase English letters.

Output

If s contains a palindrome of length exactly 100 as a subsequence, print any palindrome of length 100 which is a subsequence of s. If s doesn't contain any palindromes of length exactly 100, print a palindrome that is a subsequence of s and is as long as possible.

If there exists multiple answers, you are allowed to print any of them.

Examples

Input

bbbabcbbb


Output

bbbcbbb


Input

rquwmzexectvnbanemsmdufrg


Output

rumenanemur

Note

A subsequence of a string is a string that can be derived from it by deleting some characters without changing the order of the remaining characters. A palindrome is a string that reads the same forward or backward.

Solution (in JAVA):

Solution:

import java.util.*;
import java.io.*;
import java.math.*;
import java.text.*;
public class Main
{
  static FastScanner in = new FastScanner(System.in);
  static StringBuilder sb = new StringBuilder();
  static DecimalFormat df = new DecimalFormat();
  static String s;
  static int N;
  public static void main(String[] args)
  {
    df.setMaximumFractionDigits(20);
    df.setMinimumFractionDigits(20);
    // String formatted = df.format(0.2);
    // Never sort array of primitive type
    // df.setRoundingMode(RoundingMode.DOWN);
    System.out.print(sb.toString());
    s = in.nextToken();
    N = s.length();
    s = " " + s;
    DP = new int[N+10][111];
    was = new boolean[N+10][111];
    cnt = new int[N+10][30];
    for (int i = 1; i <= N; i++)
    {
      cnt[i][s.charAt(i)-'a']++;
      for (char ch = 'a'; ch <= 'z'; ch++)
        cnt[i][ch-'a'] += cnt[i-1][ch-'a'];
    }
//    System.out.println("findIndex(N,'c') = " + findIndex(N,'c'));

    for (int len = 100; len >= 1; len--)
    {
      if (dp(N,len) < INF)
      {
        // print the answer
        Stack<Character> stk = new Stack<Character>();
        int curind = N;
        int curlen = len;
        while (curlen > 1)
        {
          if (dp(curind,curlen) == 1+dp(curind-1,curlen))
          {
            curind--;
            continue;
          }
          System.out.print(s.charAt(curind));
          stk.add(s.charAt(curind));
          curind--;
          curlen-=2;
        }
        if (curlen == 1)
          System.out.print(s.charAt(curind));
        while (!stk.empty())
        {
          System.out.print(stk.pop());
        }
        System.out.println();

        return;
      }
    }

  }
  static int DP[][];
  static int P[][];
  static boolean was[][];
  static int cnt[][];
  static int INF = 1<<30;
  static int dp(int n, int len)
  {
    int x = DP[n][len];
    if (was[n][len]) return x;
    was[n][len] = true;
    x = INF;
    if (len == 0)
    {
      x = 0;
    }
    else if (len == 1)
    {
      x = 1;
    }
    else if (n == 0)
    {
      x = INF;
    }
    else
    {
      x = Math.min(x,1+dp(n-1,len));
      if (len >= 2)
      {
        int rec = dp(n-1,len-2);
        if (rec < INF)
        {
          int ind = findIndex(n-1-rec,s.charAt(n));
          if (ind >= 1)
          {
            x = Math.min(x,n-ind+1);
          }
        }
      }
    }
    if (x < 0)
    {
      System.out.println("wrong");
    }
    return DP[n][len] = x;
  }
  // find max i <= n
  // such that
  // s[i] == ch
  static int findIndex(int n, char ch)
  {
    if (n < 1) return -1;
    if (cnt[n][ch-'a'] == 0) return -1;
    if (s.charAt(n) == ch) return n;
    // find minimum j such that
    // cnt[j][ch] == cnt[n][ch]
    int bad = 0;
    int good = n;
    while (bad+1<good)
    {
      int m = (good+bad)/2;
      if (cnt[m][ch-'a'] == cnt[n][ch-'a'])
        good = m;
      else
        bad = m;
    }
    return good;
  }
  static BigInteger b(long n) { return BigInteger.valueOf(n);}
  static BigInteger b(String s) { return new BigInteger(s); }
  static BigDecimal bd(double d) { return BigDecimal.valueOf(d);}
  static BigDecimal bd(String s) { return new BigDecimal(s); }
}
class FastScanner
{
  BufferedReader reader;
  StringTokenizer tokenizer;
  FastScanner (InputStream inputStream)
  {
    reader = new BufferedReader(new InputStreamReader(inputStream));
  }
  String nextToken()
  {
    while (tokenizer == null || ! tokenizer.hasMoreTokens())
    {
      try {
        tokenizer = new StringTokenizer(reader.readLine());
      } catch (Exception e){}
    }
    return tokenizer.nextToken();
  }
  boolean hasNext()
  {
    if (tokenizer == null || ! tokenizer.hasMoreTokens())
    {
      try {
        tokenizer = new StringTokenizer(reader.readLine());
      } catch (Exception e){ return false; }
    }
    return true;
  }
  int nextInt()
  {
    return Integer.parseInt(nextToken());
  }
}