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.Arrays;
import java.util.Scanner;


public class Main {
  public static void main(String args[]){
    
    Scanner in = new Scanner(System.in);
    
    c = in.next().toCharArray();
    
    if(c.length >= 2600){
      int count[] = new int[26];
      for (int i = 0; i < c.length; i++) {
        count[c[i] - 'a']++;
      }
      for (int i = 0; i < 26; i++) {
        if(count[i] >= 100){
          for (int j = 0; j < 100; j++) {
            System.out.print((char)(i + 'a'));
          }
          return ;
        }
      }
    }
    else {
      dp = new int[c.length][c.length];
      for (int i = 0; i < dp.length; i++) {
        for (int j = 0; j < dp.length; j++) {
          dp[i][j] = -1;
        }
      }
      find(0, c.length - 1);
      trace(0, c.length - 1);
      
      if(res.length() < 100) 
        System.out.println(res.toString());
      else 
        System.out.println(res.substring(0, 50) + res.substring(res.length() - 50));
    }
    
  }
  
  
  private static void trace(int i, int j) {
    if(i > j)
      return ;
    else if(i == j)
      res.append(c[i]);
    else if(c[i] == c[j]){
      res.append(c[i]);
      trace(i + 1, j - 1);
      res.append(c[j]);
    }
    else {
      if(dp[i + 1][j] > dp[i][j - 1])
        trace(i + 1, j);
      else
        trace(i, j - 1);
    }
  }


  static char c[];
  static StringBuilder res = new StringBuilder("");
  
  static int dp[][];
  private static int find(int i, int j) {
    if(i > j)
      return dp[i][j] = 0;
    else if(dp[i][j] != -1)
      return dp[i][j];
    else if(i == j)
      return 1;
    else if(c[i] == c[j])
      return dp[i][j] = 2 + find(i + 1, j - 1);
    else 
      return dp[i][j] = Math.max(find(i + 1, j), find(i, j - 1));
  }
}