//#include "grader.cpp"
#include <vector>
#include <iostream>
using namespace std;
const int MAXN = 1e6 + 5;
struct SegmentTree
{
char val;
SegmentTree *L, *R;
void build(int l, int r)
{
if(l==r) return;
L = new SegmentTree();
R = new SegmentTree();
L->build(l, (l+r)/2);
R->build((l+r)/2+1, r);
}
void update(int q, char c, int l, int r, SegmentTree *other)
{
if(l==r)
{
val = c;
return;
}
if(l<=q && q<=(l+r)/2)
{
L = new SegmentTree();
L->update(q, c, l, (l+r)/2, other->L);
}
else
{
L = other->L;
}
if((l+r)/2+1<=q && q<=r)
{
R = new SegmentTree();
R->update(q, c, (l+r)/2+1, r, other->R);
}
else
{
R = other->R;
}
}
char getChar(int q, int l, int r)
{
if(l==r) return val;
if(l<=q && q<=(l+r)/2) return L->getChar(q, l, (l+r)/2);
return R->getChar(q, (l+r)/2+1, r);
}
};
struct String
{
int sz;
SegmentTree *s;
String(){}
String(int sz)
{
this->sz = sz;
this->s = new SegmentTree();
}
};
int COMMAND = 0;
String state[MAXN];
void Init()
{
cout << sizeof(SegmentTree) << '\n';
state[0] = String(0);
state[0].s->build(0, MAXN);
}
void TypeLetter(char L)
{
COMMAND++;
state[COMMAND].sz = state[COMMAND-1].sz + 1;
state[COMMAND].s = new SegmentTree();
state[COMMAND].s->update(state[COMMAND].sz-1, L, 0, MAXN, state[COMMAND-1].s);
}
void UndoCommands(int U)
{
COMMAND++;
state[COMMAND] = state[COMMAND-1-U];
}
char GetLetter(int P)
{
return state[COMMAND].s->getChar(P, 0, MAXN);
}
