CF1178E Archaeology

Alice 购买了 Congo Prime Video 的订阅，并正在观看一部关于苏格兰洛赫凯特林的 Factor's Island 上考古发现的纪录片。考古学家们发现了一本书，其年代和起源均不详。也许 Alice 能从中发现些什么？ 这本书只包含由字符 "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"（不含引号）。

在第一个样例中，其他合法答案包括 "cacac"、"caac"、"aca" 和 "ccc"。 由 ChatGPT 4.1 翻译