给定一个字符串 s,确定它是否包含任何长度正好为 100 的回文序列作为子序列。如果有,请打印其中任何一个。如果没有,则打印一个回文,它是 s 的子序列,并且尽可能长。
输入
输入中唯一一行包含一个长度为 n (1 ≤ n ≤ 5·104) 且仅包含小写英文字母的字符串 s。
输出
如果 s 包含一个长度正好为 100 的回文序列作为子序列,则打印作为 s 的子序列的任何长度为 100 的回文。如果 s 不包含任何长度正好为 100 的回文,则打印作为 s 的子序列且尽可能长的回文。
如果存在多个答案,您可以打印其中任何一个。
示例
输入 #1
bbbabcbbb
输出 #1
bbbcbbb
输入 #2
rquwmzexectvnbanemsmdufrg
输出 #2
rumenanemur
注意
字符串的子序列是可以通过删除一些字符而不改变剩余字符的顺序而从中派生的字符串。回文是向前或向后读相同的字符串。