CF1178E.Archaeology

Alice bought a Congo Prime Video subscription and was watching a documentary on the archaeological findings from Factor's Island on Loch Katrine in Scotland. The archaeologists found a book whose age and origin are unknown. Perhaps Alice can make some sense of it?

The book contains a single string of characters "a", "b" and "c". It has been pointed out that no two consecutive characters are the same. It has also been conjectured that the string contains an unusually long subsequence that reads the same from both sides.

Help Alice verify this by finding such subsequence that contains at least half of the characters of the original string, rounded down. Note that you don't have to maximise the length of it.

A string $a$ is a subsequence of a string $b$ if $a$ can be obtained from $b$ by deletion of several (possibly, zero or all) characters.

爱丽丝购买了刚果Prime Video订阅服务，正在观看一部关于苏格兰洛赫卡特琳湖（Loch Katrine）上因子岛（Factor's Island）考古发现的纪录片。考古学家发现了一本年代与来源均不明的古书。或许爱丽丝能从中解读出一些线索？

这本书仅包含由字符 “a”、“b” 和 “c” 组成的一个字符串。人们已指出：该字符串中不存在两个相邻字符相同的情况。此外，有人推测该字符串包含一个异常长的回文子序列（即正读与反读均相同的子序列）。

请帮助爱丽丝验证这一推测：找出一个长度至少为原字符串长度一半（向下取整）的回文子序列。注意：你无需使该子序列的长度最大化。

若字符串 $a$ 可通过对字符串 $b$ 删除若干个（可能为零个或全部）字符而得到，则称 $a$ 是 $b$ 的一个子序列。

The input consists of a single string $s$ ($2 \leq |s| \leq 10^6$). The string $s$ consists only of characters "a", "b", "c". It is guaranteed that no two consecutive characters are equal.

输入为一个字符串 $s$（$2 \leq |s| \leq 10^6$）。字符串 $s$ 仅由字符 "a"、"b"、"c" 组成。保证不存在两个相邻的字符相等。

Output a palindrome $t$ that is a subsequence of $s$ and $|t| \geq \lfloor \frac{|s|}{2} \rfloor$.

If there are multiple solutions, you may print any of them. You don't have to maximise the length of $t$.

If there are no solutions, output a string "IMPOSSIBLE" (quotes for clarity).

输出字符串 $s$ 的一个回文子序列 $t$，满足 $|t| \geq \lfloor \frac{|s|}{2} \rfloor$。

若存在多个解，输出任意一个即可。你无需使 $t$ 的长度最大化。

若无解，则输出字符串 "IMPOSSIBLE"（引号仅作清晰标识之用）。

In the first example, other valid answers include "cacac", "caac", "aca" and "ccc".

在第一个示例中，其他有效的答案还包括 “cacac”、“caac”、“aca” 和 “ccc”。