問題 D - unbalanced

Time Limit: 2 seconds / Memory Limit: 256 MB

問題

うさぎはある文字列 S を眺めている．文字列 S に左右のバランスの悪さを感じたうさぎは，S から何文字かを消して回文にしてしまおうと考えた．回文とは，左から読んでも右から読んでも文字の並びが同じであるような文字列のことである．

消した文字たちを S での相対的な順番を保ったまま並べると新たな文字列 T が得られる．T として考えられる辞書順最小の文字列を求めよう．ただし，文字列 a が文字列 b より辞書順で小さいとは，a が b の接頭辞であるか，a と b を先頭の文字から順に比較した際に最初に異なる箇所で a の方が早い文字であること，として定義される．

入力

S

1 行目は文字列 S を含む．

出力

T として考えられる辞書順最小の文字列を 1 行に出力せよ．

制約

• 2 ≤ (S の長さ) ≤ 100．
• S はアルファベット大文字からなる．
• S は回文ではない．

部分点

100 点中 25 点分のデータは以下を満たす．

• 2 ≤ (S の長さ) ≤ 15．

入出力例

入力例 1

EXAMPLE

出力例 1

AMPL

入力例 2

URTAMMBBTIUT

出力例 2

RABBIT

入力例 3

OOOOOOOOOOOOOOQ

出力例 3

OOOOOOOOOOOOOO