题目描述

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

请你求出 $S$ 的一个不一定连续的子序列 $x$，使得 $x$ 满足以下所有条件，并且在所有满足条件的子序列中长度最长。子序列指的是从 $S$ 中删除 $0$ 个或多个字符后得到的字符串。

• $x$ 中包含的 A、B、C 的数量都相等。
• 在 $x$ 中，相同的字符不会相邻出现。

输入格式

输入从标准输入读取，格式如下：

$S$

输出格式

请输出满足条件的最长子序列中的一个。如果有多个答案，输出其中任意一个都视为正确。

输入输出样例 #1

输入 #1

ABBCBCAB

输出 #1

ACBCAB

输入输出样例 #2

输入 #2

ABABABABACACACAC

输出 #2

BABCAC

输入输出样例 #3

输入 #3

ABCABACBCBABABACBCBCBCBCBCAB

输出 #3

ACABACABABACBCBCBCBCA

输入输出样例 #4

输入 #4

AAA

输出 #4

说明/提示

限制

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

样例解释 1

以 $S$ 的子序列 ACBCAB 为例，它满足所有条件，并且是最长的。ABCBCA 也是满足条件的最长子序列。ABCBCAB、ABBCCA 等虽然是 $S$ 的子序列，但不满足条件。

样例解释 4

有时，唯一满足条件的子序列可能是空字符串。