#include <bits/stdc++.h>
using namespace std;
#define mkp make_pair
vector<char> segtree(1000010*20,' ');
vector<int> lef(1000010*20),righ(1000010*20),root(1000010),siz(1000010);
int i=1,v=0;
void update(int exr, int newr, int l, int r, int x, char j){
lef[newr]=lef[exr];
righ[newr]=righ[exr];
segtree[newr]=segtree[exr];
if(l==r){
segtree[newr]=j;
return;
}
int m=l+((r-l)/2);
if(x<=m){
i++;
lef[newr]=i;
update(lef[exr],lef[newr],l,m,x,j);
}else{
i++;
righ[newr]=i;
update(righ[exr],righ[newr],m+1,r,x,j);
}
}
char query(int root, int l, int r, int x){
if(l==r)return segtree[root];
int m=l+((r-l)/2);
if(x<=m)return query(lef[root],l,m,x);
else return query(righ[root],m+1,r,x);
}
void Init() {
v=0;
root[v]=v;
siz[v]=v;
v++;
}
void TypeLetter(char L) {
i++;
root[v]=i;
siz[v]=siz[v-1]+1;
update(root[v-1],root[v],0,1000000,siz[v-1],L);
v++;
}
void UndoCommands(int U) {
int target=v-1-U;
root[v]=root[target];
siz[v]=siz[target];
v++;
}
char GetLetter(int P) {
return query(root[v-1],0,1000000,P);
}
