题目描述

给定一个字符串 $S$，请从中找出字典序最大的回文子序列。

• 子序列：从原字符串中抽取若干个字符（可以不连续），保持它们在原字符串中的相对顺序排列形成的新序列。例如，字符串 abc 的子序列包括 a、b、c、ab、ac、bc 和 abc。
• 回文：正读和反读都相同的字符串。例如 aa、aba、abba 都是回文。
• 字典序：从左到右逐字符比较，先出现较大字符的字符串字典序更大；若较短字符串是较长字符串的前缀，则较短的字典序更小。例如 abc \lt abd，而 ab \lt abc。

请找出 $S$ 中字典序最大的回文子序列。

输入格式

输入一行包含一个字符串 $S$。

输出格式

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

样例

abcd

d

abab

bb

提示

评测用例规模与约定

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