#include <bits/stdc++.h>
#include "grader.h"

#pragma GCC optimize("O3,unroll-loops")

using namespace std;
using ll = long long;

int char_to_index(char x) {
	if (x == 'A') return 0;
	if (x == 'C') return 1;
	if (x == 'G') return 2;
	if (x == 'T') return 3;
	throw 1;
}

struct Node {
	Node *l, *r;

	int cnt[4], prior, siz;
	char c;

	Node(char x) {
		c = x;
		fill(cnt, cnt+4, 0);
		cnt[char_to_index(x)]++;
		prior = rand();
		siz = 1;
		l = r = nullptr;
	}
};

int get_size(Node *ptr) {
	return ptr ? ptr->siz : 0;
}

void pull(Node *v) {
	v->siz = 1 + get_size(v->l) + get_size(v->r);
	fill(v->cnt, v->cnt+4, 0);
	v->cnt[char_to_index(v->c)] = 1;
	if (v->l) {
		for (int i = 0; i < 4; i++) {
			v->cnt[i] += v->l->cnt[i];
		}
	}
	if (v->r) {
		for (int i = 0; i < 4; i++) {
			v->cnt[i] += v->r->cnt[i];
		}
	} 
}

Node *merge(Node *l, Node *r) {
	if (!l || !r) return l ? l : r;
	if (l->prior > r->prior) {
		l->r = merge(l->r, r);
		pull(l);
		return l;
	} else {
		r->l = merge(l, r->l);
		pull(r);
		return r;
	}
}

pair<Node *, Node *> split(Node *v, int x) {
	if (!v) return {nullptr, nullptr};
	if (get_size(v->l) < x) {
		auto [l, r] = split(v->r, x - 1 - get_size(v->l));
		v->r = l;
		pull(v);
		return {v, r};
	} else {
		auto [l, r] = split(v->l, x);
		v->l = r;
		pull(v);
		return {l, v};
	}
}

Node *root = nullptr;

void Kezd(string s) {
	srand(4);
	for (char c : s) {
		root = merge(root, new Node(c));
	}
}

void Beszur(int i, char x) {
	auto [a, b] = split(root, i);
	root = merge(a, merge(new Node(x), b));
}

void Mutal(int i, char x) {
	auto [a, b] = split(root, i-1);
	auto [c, d] = split(b, 1);
	root = merge(a, merge(new Node(x), d));
}

void Kivag(int i, int j) {
	auto [a, b] = split(root, i-1);
	auto [c, d] = split(b, j-i+1);
	root = merge(a, d);
}

int Szamlal(int i, int j, char x) {
	auto [a, b] = split(root, i-1);
	auto [c, d] = split(b, j-i+1);
	int res = c->cnt[char_to_index(x)];
	root = merge(a, merge(c, d));
	return res;
}

string Eredmeny() {
	if (!root) return "";
	string res;
	stack<Node *> st;
	Node *v = root;
	while (v) {
		st.push(v);
		v = v->l;
	}
	auto next = [&](){
		Node *u = st.top();
		if (u->r) {
			u = u->r;
			while (u) {
				st.push(u);
				u = u->l;
			}
		} else {
			while (true) {
				st.pop();
				if (st.empty()) return;
				Node *par = st.top();
				if (par->l == u) return;
				u = par;
			}
		}
	};
	while (!st.empty()) {
		res += st.top()->c;
		next();
	}
	return res;
}
/*
int main() {
	string s; cin >> s;
	Kezd(s);
	while (true) {
		int op; cin >> op;
		cerr << op << endl;
		if (op == 0) {
			break;
		}
		if (op == 1) {
			int x; char c; cin >> x >> c;
			Beszur(x, c);
		}
		if (op == 2) {
			int x; char c; cin >> x >> c;
			Mutal(x, c);
		}
		if (op == 3) {
			int l, r; cin >> l >> r;
			Kivag(l, r);
		}
		if (op == 4) {
			int l, r, ans; char c; cin >> l >> r >> c >> ans;
			int res = Szamlal(l, r, c);
			// if (ans == res) cout << "Correct\n";
			// else cout << "Incorrect: " << ans << " " << res << "\n";
		}
		if (op == 5) {
			string res = Eredmeny();
			string ans; cin >> ans;
			ans.pop_back();
			// if (ans == res) cout << "Correct\n";
			// else cout << "Incorrect: " << ans << " " << res << "\n";
		}
		cout << Eredmeny() << "\n";
	}
}
*/