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.io.*;
import java.util.*;

public class B {
  static int LIM = 26*99;
  static char[] inp = null;
  static int[][] memo = null;
  static int go(int i, int j) {
    return memo[i][j] =
      memo[i][j] != -1 ? memo[i][j] :
      i == j ? 1 :
      i == j - 1 && inp[i] == inp[j] ? 2 :
      inp[i] == inp[j] ? 2 + go(i + 1, j - 1) :
      Math.max(go(i + 1, j), go(i, j - 1));
  }
  
  static String cp(int x, int y) {
    String ret = "";
    for (int i = 0; i < y; i++) {
      ret += (char)(x);
    }
    return ret;
  }
  
  public static void main(String[] args) throws Throwable {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    inp = in.readLine().toCharArray();
    if (inp.length > LIM) {
    /*
    CUUUUURRRSSSE YOOOOOUUUU, PIGEONHOOOOLLLEEEE!!!!
,,,,,,,,,,,,,,,,,,,,..,.........................................................
,,,,,,,,,,,,,,,,,,,,............................................................
,,,,,,,,,,,,,,,,,,,.............................................................
,,,,,,,,,,,,,,,,,,,,............................................................
,,,,,,,,,,,,,,,,,,,,.........................................?7I??+.............
,,,,,,,,,,,,,,,,,,,,,......................................77$=Z$$Z$$...........
,,,,,,,,,,,,.,,,,,,,,,.,..................................7$$$Z7OZZZZ,..........
,,,,,,,,,.,,,,,,,,,,,,.,,,...............................I$ZO+O?IZZ=~?,.........
,,,,,,,,,,,,,,,.,,,,.,..,...............................I7ZZZZZZ?====?=....,...,
,,,,,,,,,,,,,,,,,....,.,...,...........................I7ZZZZZZZZZ?$+?:........,
,,,,,,,,,,,,,,,,.,,.,,,,,.,,,..........................7ZOOZZ$$Z$$$~II7.,.....,,
,,,,,,,,,,,,,,,,,,,,,..,..,...........................7$ZZZZZZZ$$$,,.??,,.,..,,,
,,,,,,,,,,,,,,,,,,,..,,,.,,..........................ZI$OOOOZZZZZZ,,....,,.,..,,
,,,,,,,,,,,,,,,,,,,.,.,,,,,...,,,..,...,............7$$ZOZOZZOZZO$,,,,.,,,,,.,.,
,,,,,,,,,,,,,,,,,,,,,,,...,...,,,..................ZI$ZOZOOOOZZOZ$,.,,,,,.,..,,,
,,,,,,,,,,,,,,,,,,,..,,,,,,.,,............,...,...+?O8ZZOOOOOOZZZ7,.,..,,,....,,
,,,,,,,,,,,,,.,,,,,,,,,,,......,..,......,.,.....I7$$ZZOOOOOOOOZZ$.,,,........,,
,,,,,,,,,,,,,.,,,,,,,,,,,...,,..,...............II$Z8OZZOOOOOOOZZZ,..,,..,.,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,..........,.,,,,.......+7$$Z$OOZOOOOOOZZZ$,...,,,..,,,,,
,,,,,,,,,,,,,,,,,,,,,,,.,.,.,....,,,,,,,,,....=?Z$ZZZZZZOOZOZOOOZ$,...,.,,,,,,,,
,,,,,,,,,,,,,,,,,,,.,,,,,,,,,,,,,,.,,,.,.....==I77ZZOZZZZZZZZZZZZ$,,.,,..,.,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,,,,.,,,.....:~=~==+I7ZZZZZZOOZZZZ$7,.,,,...,,.,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,.,,,,.,,..,,.,:~====+++==+ZZZZZZZZZZ$7...,,........,
,,,,.,,.,,,,,,,.,,,,,,,,,,,,,,,,,,,,,,,.:~~~======++=++++=ZZZ$Z$$7.,,.,......,,,
,,,,,,..,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:~~==============++++=$$7$7I..,,,.,....,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:~~~=================+++77777I...,,,......,,
,,,,,,,,..,,,,,,,,,,,,,,,,,,,,,,,,,:~~~===================+++777I?..,,,,,,.,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:~~~~===================++?7III?,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,::::~~~==================++I7II??,,,,,,,,,,,,,,
,,,,,,..,,,,,,,,,,,,,,,,,,,,,,,=~~~~~~=~~~~~===~=========+++II???,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,.,,,,,,,,,,,,,,$$:~=~~~~~=~=~===~==========++?+??+?,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,.,,,,,,,,,.,ZZZ~~+?~~~~~=~=~==~==========+??+?+,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,,.,,.?Z~ZZZZ+==~~~~~=~~~=~=========+7++++=,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,.,,,$~ZO~=ZOOZ+==~~==~~~====~=~====+?+=+=,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,.I?ZZZO=~~OOOOO$~~~~~~~=+====+==??::+=,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,,,=+~~OOOO~~~~7OOOO==~~====~~===$+:::~,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,,,,,,,,,,ZZZ~~~~ZOOZ=~~~==7OOOO7ZZ~~==II+::,:,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,.,,..,.Z$ZZZZZ$7+IO$OO~~~~~~=========~~:,::,,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,,,..,Z:~ZZZZZZ$$77$$Z7ZZI==~~~===~~~~~:~~::...,,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,.$ZZ:::Z$Z$$$7$77I+~:~ZZ$$$?+==~=~~~~~::::....,,,,,,,,,,,,,,,,,,,,,,,,,,,
..,...,ZZ$:::=$,:::::,I$7$I$$~~:~:~~~~~:~~~~~::......,.,,,,,,,,,,,,,,,,,,,,,,,,,
......,:?II777???=,...............:::~~~:::~~:,.........,,,,,,,,,,,,,,,,,,,,,,,,
,,.,IZ$?777~.........................::~:::~:+++,.......,,,,,,,,,,,,,,,,,,,,,,,,
,,,=ZO?,...............................,:::::77I=:7+..,,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,,:~~~~~~~:,..,,,,....................~+++,?$$Z?..,,,,,,,,,,,,,,,,,,,,,,,,,
,,,,,,...,,,,,,::::::::....................I+.?+??....++,,,,,,,,,,:,,,:,,,::::::
,,,,,.......,,,,,,,,,,,::::,,,...........,:::$+++?~777I~::::::::::::::::::::::::
,,,,............,,,,,,,,,,,,,,,,,,.....,,,,,...::=+++::$???~~::~~::~:~~~~~~::~~~
,,,...............,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,:.....~~~~~~~~~~~~~~~~~~~~~~~
,,..................,,,,,,,,,,,,,,,,,,,,,,,,,,,,....,....~~~:~~=~~~~~~~~=~~~~~~~
,....................,.,,,,,,,,,,,,,,,,,,,,,,,,,,,........~~~~~~~~~~~~~~~~~~~~~~
.......................,,,,,,,,,,,,,,,,,,,,,,,,,,,,.......::::~:::,:::~:::::::~:
*/
      Arrays.sort(inp);
      char lah = 'a', prev = '0';
      int ct = 0;
      for (char c : inp) {
        if (c == prev) {
          ct++;
        } else {
          ct = 1;
          prev = c;
        }
        
        if (ct >= 100) {
          System.out.println(cp(prev, 100));
          System.exit(0);
        }
      }
    } else {
      memo = new int[inp.length][inp.length];
      for (int i = 0; i < inp.length; i++) {
        for (int j = 0; j < inp.length; j++) {
          memo[i][j] = -1;
        }
      }
      go(0, inp.length - 1);
      int best = memo[0][inp.length - 1];
      char[] op = new char[Math.min(100, best)];
      int i = 0, j = inp.length - 1;
      int ind = 0;
      while (ind < (op.length + 1) / 2) {
        while (i + 1 < j && memo[i + 1][j] == memo[i][j]) {
          i++;
        }
        while (i < j - 1 && memo[i][j - 1] == memo[i][j]) {
          j--;
        }
        op[ind] = inp[i];
        op[op.length - 1 - ind] = inp[i];
        ind++;
        i++;
        j--;
      }
      System.out.println(new String(op));
    }
  }
}