ABC String

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.

Examples

Input

ABBCBCAB

Output

ACBCAB

Input

ABABABABACACACAC

Output

BABCAC

Input

ABCABACBCBABABACBCBCBCBCBCAB

Output

ACABACABABACBCBCBCBCA

Input

AAA

Output

inputFormat

Input

Input is given from Standard Input in the following format:

S

outputFormat

Output

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

Examples

Input

ABBCBCAB

Output

ACBCAB

Input

ABABABABACACACAC

Output

BABCAC

Input

ABCABACBCBABABACBCBCBCBCBCAB

Output

ACABACABABACBCBCBCBCA

Input

AAA

Output

样例

ABABABABACACACAC

BABCAC