Hello Codeforces,

//1-based indexing for everything
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000005; //just an arbitrarily high limit 
struct Segtree{
    int vcnt, root[MAX_N], rootCnt;
	char f[MAX_N * 22];
    int lc[MAX_N * 22], rc[MAX_N * 22];
	void createNode(int &x){ x = ++vcnt; }
    void build(int &x, int l, int r){
        if(x == 0) createNode(x);
        if(l == r){
            f[x] = 0;
            return;
        }
        int mid = (l + r) / 2;
        build(lc[x], l, mid);
        build(rc[x], mid + 1, r);
    }
    void update(int &x, int l, int r, int oldX, int pos, int val){
        if(x == 0) createNode(x);
        if(l == r){
            f[x] = val; //Set leaf node to new value
            return;
        }
        int mid = (l + r) / 2;
        if(pos <= mid){
            update(lc[x], l, mid, lc[oldX], pos, val);
            rc[x] = rc[oldX];
        } else {
            update(rc[x], mid + 1, r, rc[oldX], pos, val);
            lc[x] = lc[oldX];
        }
    }
    char query(int x, int l, int r, int q){
        if(x == 0) return 0;
		if(l == r) return f[x];
		int mid = (l + r) / 2;
		if(q <= mid) return query(lc[x], l, mid, q); else return query(rc[x], mid+1, r, q);
    }
};
int chs[MAX_N]; //count of chars in i'th revision, also index of last char because of 1-based indexing
Segtree T;
int sz = 1000001; //size of our "char array"
void Init() {
	T.build(T.root[++T.rootCnt], 1ll, sz);
}
void TypeLetter(char x) {
	T.rootCnt++;
	T.update(T.root[T.rootCnt], 1, sz, T.root[T.rootCnt-1], chs[T.rootCnt-1]+1, x);
	chs[T.rootCnt] = chs[T.rootCnt-1] + 1;
}
void UndoCommands(signed g) {
	T.rootCnt++;
	T.root[T.rootCnt] = T.root[T.rootCnt-g-1];
	chs[T.rootCnt] = chs[T.rootCnt-g-1];
} 
char GetLetter(signed p) {
	return T.query(T.root[T.rootCnt], 1, sz, p+1);
}