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
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
#else
#define db(x) 0
#define db2(x, y) 0
#define db3(x, y, z) 0
#define dbv(v) 0
#define dba(a, n) 0
#endif
typedef long long ll;
typedef long double ld;
char S[1000005];
vector<string> split(string s, char delim) {
	string cur;
	vector<string> ret;
	for (char c : s) {
		if (c == delim) {
			ret.push_back(cur);
			cur.clear();
		} else cur += c;
	}
	ret.push_back(cur);
	return ret;
}
int main() {
	scanf("%s", S);
	int n = strlen(S);
	n = unique(S, S + n) - S;
	S[n] = '\0';
	vector<int> cnt(3), singleCnt(3);
	for (int i = 0; i < n; ++i) ++cnt[S[i] - 'A'];
	int a = min_element(cnt.begin(), cnt.end()) - cnt.begin();
	fill(cnt.begin(), cnt.end(), 0);
	auto subs = split(string(S), 'A' + a);
	for (int i = 0; i < subs.size(); ++i) {
		if (i > 0 && i + 1 < subs.size() && subs[i].size() == 1) {
			++singleCnt[subs[i][0] - 'A'];
		}
		vector<bool> has(3);
		for (char x : subs[i]) has[x - 'A'] = true;
		for (int j = 0; j < 3; ++j)
			if (has[j]) ++cnt[j];
	}
	assert(cnt[a] == 0 && singleCnt[a] == 0);
	int b = a == 0 ? 1 : 0;
	int c = a == 2 ? 1 : 2;
	if (singleCnt[b] > cnt[c]) {
		swap(b, c);
	}
	assert(singleCnt[b] <= cnt[c]);
	if (singleCnt[c] > cnt[b]) {
		dbv(subs);
		db(singleCnt[c]);
		string cs;
		cs += c + 'A';
		vector<string> res = {subs[0]};
		for (int i = 1; i < subs.size(); ++i) {
			if (subs[i] == cs && singleCnt[c] > cnt[b]) {
				--singleCnt[c];
				res.back() += c + 'A';
			} else {
				res.push_back(subs[i]);
			}
		}
		subs = res;
	}
	dbv(subs);
	assert(singleCnt[c] <= cnt[b]);
	string ans;
	fill(cnt.begin(), cnt.end(), 0);
	for (int i = 0; i < subs.size(); ++i) {
		subs[i].erase(unique(subs[i].begin(), subs[i].end()), subs[i].end());
		for (char x : subs[i]) ++cnt[x - 'A'];
	}
	cnt[a] = (int)subs.size() - 1;
	if (cnt[b] > cnt[c]) swap(b, c);
	dbv(subs);
	assert(cnt[c] >= cnt[a]);
	assert(cnt[b] >= cnt[a]);
	for (int i = 0; i < subs.size(); ++i) {
		int lb = (i == 0 || i + 1 == subs.size()) ? 0 : 1;
		while (cnt[c] > cnt[b] && subs[i].size() >= lb + 1 && subs[i].back() == 'A' + c) {
			subs[i].pop_back();
			--cnt[c];
		}
		while (cnt[c] > cnt[b] && subs[i].size() >= lb + 1 && subs[i][0] == 'A' + c) {
			subs[i].erase(subs[i].begin());
			--cnt[c];
		}
	}
	assert(cnt[c] == cnt[b]);
	dbv(cnt);
	dbv(subs);
	for (int i = 0; i < subs.size(); ++i) {
		int lb = (i == 0 || i + 1 == subs.size()) ? 0 : 1;
		while (cnt[b] > cnt[a] && subs[i].size() >= lb + 2) {
			subs[i].pop_back();
			subs[i].pop_back();
			--cnt[b];
		}
		if (i) ans += a + 'A';
		ans += subs[i];
	}
	printf("%s\n", ans.c_str());
}
