#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
struct node{
char val;
node* l;
node* r;
};
int n,cur;
int sz[maxn];
node* root[maxn];
void build(node* pos,int l,int r) {
if(l==r) return ;
int mid = (l+r)/2;
pos->l = new node; pos->r = new node;
build(pos->l,l,mid); build(pos->r,mid+1,r);
}
void upgrade(node* pos,node* last,int l,int r,int x,int val) {
if(l==r) {
pos->val = val;
return ;
}
int mid = (l+r)/2;
if(x<=mid) {
pos->l = new node;
pos->r = last->r;
upgrade(pos->l,last->l,l,mid,x,val);
}
else {
pos->l = last->l;
pos->r = new node;
upgrade(pos->r,last->r,mid+1,r,x,val);
}
}
char query(node* pos,int l,int r,int x) {
if(l==r) return pos->val;
int mid = (l+r)/2;
if(x<=mid) return query(pos->l,l,mid,x);
return query(pos->r,mid+1,r,x);
}
void Init() {
root[0] = new node;
sz[0] = -1;
build(root[0],0,1000000);
}
void TypeLetter(char L) {
cur++;
root[cur] = new node;
sz[cur] = sz[cur-1] + 1;
upgrade(root[cur],root[cur-1],0,1000000,sz[cur],L);
}
void UndoCommands(int U) {
cur++;
root[cur] = root[cur-U-1];
sz[cur] = sz[cur-U-1];
}
char GetLetter(int P) {
return query(root[cur],0,1000000,P);
}
