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

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);
	for (int i = 0; i < 4; i++) {
		v->cnt[i] = (char_to_index(v->c) == i);
		if (v->l) v->cnt[i] += v->l->cnt[i];
		if (v->r) 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};
	}
}

void print(Node *v, string &res) {
	if (v->l) print(v->l, res);
	res += v->c;
	if (v->r) print(v->r, res);
}

Node *root = nullptr;

void Kezd(string s) {
	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() {
	string res;
	print(root, res);
	return res;
}