#include "bits/stdc++.h"
#define pb push_back
using namespace std;
struct node{
int l,r;
char val;
};
const int MAXN = 23931670;
node a[MAXN];
int sto=-1;
vector<int>version_roots;
vector<int>version_wordlens;
int cnt=0;
int build(int L,int R){
int next_node=++sto;
if(L==R){
a[next_node].val='.';
return next_node;
}
int mid=(L+R)/2;
a[next_node].l=build(L,mid);
a[next_node].r=build(mid+1,R);
return next_node;
}
int update(int node,char yes,int L,int R,int tar){
int next_node=++sto;
if(L==R){
a[next_node].val=yes;
return next_node;
}
int mid=(L+R)/2;
if(tar<=mid){
a[next_node].l=update(a[node].l,yes,L,mid,tar);
a[next_node].r=a[node].r;
}
else{
a[next_node].l=a[node].l;
a[next_node].r=update(a[node].r,yes,mid+1,R,tar);
}
return next_node;
}
char query(int node,int L,int R,int tar){
if(L==R){
return a[node].val;
}
int mid=(L+R)/2;
if(tar<=mid){
return query(a[node].l,L,mid,tar);
}
else{
return query(a[node].r,mid+1,R,tar);
}
}
void Init(){
build(1,1000000);
version_roots.pb(0);
version_wordlens.pb(0);
}
void TypeLetter(char L){
cnt++;
version_roots.pb(sto+1);
version_wordlens.pb(version_wordlens[cnt-1]+1);
update(version_roots[cnt-1],L,1,1000000,version_wordlens[cnt]);
}
void UndoCommands(int U){
cnt++;
version_roots.pb(sto+1);
version_wordlens.pb(version_wordlens[cnt-U-1]);
int next_node=++sto;
a[next_node].l=a[version_roots[cnt-U-1]].l;
a[next_node].r=a[version_roots[cnt-U-1]].r;
}
char GetLetter(int P){
P++;
return query(version_roots[cnt],1,1000000,P);
}
