Problem Statement

Given is a string $S$ consisting of A,B, and C.

Consider the (not necessarily contiguous) subsequences $x$ of $S$ that satisfy all of the following conditions:

• A, B, and C all occur the same number of times in $x$.
• No two adjacent characters in $x$ are the same.

Among these subsequences, find one of the longest. Here a subsequence of $S$ is a string obtained by deleting zero or more characters from $S$.

Constraints

• $1 \leq |S| \leq 10^6$
• $S$ consists of A,B, and C.

Input

Input is given from Standard Input in the following format:

S

Output

Print one longest subsequence that satisfies the conditions. If multiple solutions exist, any of them will be accepted.