Alice 购买了 Congo Prime Video 订阅,正在观看一部关于苏格兰卡特琳湖 Factor's Island 考古发现的纪录片。考古学家发现了一本年代和起源不明的书。也许爱丽丝能理解一些?
本书包含单个字符串“a”、“b”和“c”。已经指出,没有两个连续的字符是相同的。人们还推测该字符串包含一个异常长的子序列,从两侧读取相同的内容。
通过找到包含原始字符串至少一半字符的子序列(向下舍入)来帮助 Alice 验证这一点。请注意,您不必最大化它的长度。
如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得,则字符串 $$$a$$$ 是字符串 $$$b$$$ 的子序列。
输入
输入由单个字符串 $$$s$$$($$$2 \leq |s| \leq 10^6$$$)组成。字符串 $$$s$$$ 仅包含字符“a”、“b”、“c”。保证没有两个连续的字符是相等的。
输出
输出一个回文 $$$t$$$,它是 $$$s$$$ 和 $$$|t| 的子序列\geq \lfloor \frac{|s|}{2} \rfloor$$$。
如果有多个解决方案,您可以打印其中任何一个。您不必最大化 $$$t$$$ 的长度。
如果没有解决方案,则输出字符串“IMPOSSIBLE”(为了清楚起见,用引号引起来)。
示例
输入 #1
cacbac
输出 #1
aba
输入 #2
abc
输出 #2
a
输入 #3
cbacacacbcbababacbcb
输出 #3
cbaaacbcaaabc
注意
在第一个示例中,其他有效答案包括“cacac”、“caac”、“aca”和“ccc”。