题目描述

在遥远的未来，星际旅行已经成为常态。宇航员小蓝在一次探险任务中，意外发现了一个古老的太空遗迹。遗迹中存放着一个数据存储器，里面记录着一段加密的信息。经过初步分析，小蓝发现这段信息可以被表示为一个字符串 $S$，而解密的关键，在于找出 $S$ 中字典序最大的回文子序列。

• 子序列：指从原字符串中抽取若干个字符（可以不连续），按照它们在原字符串中的相对顺序排列所形成的新序列。例如，对于字符串 abc，其子序列包括 a、b、c、ab、ac、bc 和 abc。
• 字典序：指字符串按照字典中的排序规则比较大小的方式。对于两个字符串，从左到右逐字符比较，先出现较大字符的字符串字典序更大；若比较到某个字符串结束仍未找到不同的字符，则较短的字符串字典序较小。例如，abc < abd，而 ab < abc。

现在，请你从字符串 $S$ 中，找出字典序最大的回文子序列，帮助小蓝解开这段来自星际文明的信息。

输入格式

输入一行包含一个字符串 $S$，表示加密的信息。

输出格式

输出一行包含一个字符串，表示 $S$ 中字典序最大的回文子序列。

abcd

d

abab

bb

提示

评测用例规模与约定

• 对于 $30\%$ 的评测用例，$1 \leq |S| \leq 300$，其中 $|S|$ 表示字符串 $S$ 的长度；
• 对于所有评测用例，$1 \leq |S| \leq 10^5$，$S$ 中只包含小写英文字母。