问题描述

给定一个由 A, B, 和 C 组成的字符串 $S$。

考虑满足以下所有条件的字符串 $x$ 是 $S$ 的一个子序列（不一定是连续的）：

• 在 $x$ 中，A, B, 和 C 出现的次数相同。
• $x$ 中相邻的两个字符不相同。

在这些子序列中，找到一个最长的子序列。这里，$S$ 的子序列是通过从 $S$ 中删除零个或多个字符得到的字符串。

约束条件

• $1 \leq |S| \leq 10^6$
• $S$ 由 A, B, 和 C 组成。

输入

输入以以下格式给出：

$S$

输出

打印满足条件的一个最长子序列。如果存在多个解决方案，则接受任何一个。

示例输入 1

ABBCBCAB

示例输出 1

ACBCAB

考虑 $S$ 的子序列 ACBCAB。它满足条件，并且是满足这些条件的最长子序列之一，还有 ABCBCA。另一方面，子序列 ABCBCAB 和 ABBCCA 不满足条件。

示例输入 2

ABABABABACACACAC

示例输出 2

BABCAC

示例输入 3

ABCABACBCBABABACBCBCBCBCBCAB

示例输出 3

ACABACABABACBCBCBCBCA

示例输入 4

AAA

示例输出 4

可能只有空字符串满足条件。