#include <bits/stdc++.h>
using namespace std;
struct node
{
char c;
int L, R;
};
int all, ver;
int root[1000005], num[1000005];
node seg[24000000];
int build(int l, int r)
{
int now = ++all;
if(l == r) return now;
int mid = (l+r)>>1;
seg[now].L = build(l, mid), seg[now].R = build(mid+1, r);
return now;
}
int update(int l, int r, int idx, int p, char c)
{
if(!(l <= p && p <= r)) return idx;
int now = ++all;
if(l == r)
{
seg[now].c = c;
return now;
}
int mid = (l+r)>>1;
int L = update(l, mid, seg[idx].L, p, c), R = update(mid+1, r, seg[idx].R, p, c);
seg[now].L = L;
seg[now].R = R;
return now;
}
char query(int l, int r, int idx, int p)
{
if(l == r) return seg[idx].c;
int mid = (l+r)>>1;
return (p <= mid) ? query(l, mid, seg[idx].L, p) : query(mid+1, r, seg[idx].R, p);
}
void Init()
{
root[0] = build(1, 1000000);
}
void TypeLetter(char L)
{
ver++;
num[ver] = num[ver-1] + 1;
root[ver] = update(1, 1000000, root[ver-1], num[ver], L);
}
void UndoCommands(int U)
{
ver++;
num[ver] = num[ver-U-1];
root[ver] = root[ver-U-1];
}
char GetLetter(int P)
{
return query(1, 1000000, root[ver], P+1);
}
