#include <bits/stdc++.h>
//#define int long long
#define INF 1000000000000000
#define lchild(i) (i*2 + 1)
#define rchild(i) (i*2 + 2)
#define mid(l, u) ((l+u)/2)
#define x(p) p.first
#define y(p) p.second
#define MOD 998244353
using namespace std;
struct node{
int l;
int r;
char val;
};
node buffer[100*(1000000)];
int cnode = 0;
int initnode(int left = -1, int right = -1, char v = 'A'){
buffer[cnode].l = left;
buffer[cnode].r = right;
buffer[cnode].val = v;
return cnode++;
}
signed version[(int)1e6 + 5];
signed ptr[(int)1e6 + 5];
signed ind = 1;
char query(int l, int u, int ll, int i){
if(l>=ll && u<=ll) return buffer[i].val;
if(ll<=mid(l, u)){
return query(l, mid(l, u), ll, buffer[i].l);
}
return query(mid(l, u)+1, u, ll, buffer[i].r);
}
int update(int l, int u, int i, int ll, char v){
//cout<<"update "<<l<<" "<<u<<" "<<ll<<" "<<v<<"\n";
if(l>=ll && u<=ll) return initnode(-1, -1, v);
int tr = initnode();
if(i!=-1) buffer[tr].l = buffer[i].l;
if(i!=-1) buffer[tr].r = buffer[i].r;
if(ll<=mid(l, u)){
buffer[tr].l = update(l, mid(l, u), buffer[tr].l, ll, v);
}
else buffer[tr].r = update(mid(l, u)+1, u, buffer[tr].r, ll, v);
return tr;
}
void Init(){
version[0] = initnode();
ptr[0] = 0;
}
void TypeLetter(char l){
version[ind] = update(0, 1000000, version[ind - 1], ptr[ind-1], l);
ptr[ind] = ptr[ind-1] + 1;
ind++;
}
void UndoCommands(signed u){
version[ind] = version[ind-1-u];
ptr[ind] = ptr[ind - 1 - u];
ind++;
}
char GetLetter(signed p){
return query(0, 1000000, p, version[ind - 1]);
}
/*signed main(){
Init();
int q;
cin>>q;
while(q--){
int type;
cin>>type;
if(type==1){
char l;
cin>>l;
TypeLetter(l);
}
else if(type==2){
int u;
cin>>u;
UndoCommands(u);
}
else{
int pos;
cin>>pos;
cout<<GetLetter(pos)<<endl;
}
}
}*/
/*
1 a
1 b
3 1
1 d
2 2
2 1
3 2
1 e
2 1
2 5
1 c
3 2
2 2
3 2
*/
