← 返回题目列表

Codeforces · 1178/E

E. 考古学

中文机器翻译题面 查看原题

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”。