#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll lim=1e6+5;
struct node{
char c;
ll p[20];
ll d;
};
node *n[lim];
ll cur=1;
void Init(){
n[0]=new node();
n[0]->c=0,n[0]->d=-1;
fill(n[0]->p,n[0]->p+20,0);
}
void TypeLetter(char L) {
n[cur]=new node();
n[cur]->d=n[cur-1]->d+1;
n[cur]->c=L;
n[cur]->p[0]=cur-1;
for(int i=1;i<20;i++){
if(n[cur]->p[i-1]==0)break;
n[cur]->p[i]=n[n[cur]->p[i-1]]->p[i-1];
}
cur++;
}
void UndoCommands(int U) {
n[cur]=n[cur-1-U];
cur++;
}
char GetLetter(int P) {
ll goup=n[cur-1]->d-P;
ll cn=cur-1;
// cerr<<"d:"<<n[cur-1]->d<<" P:"<<P<<" goup:"<<goup<<"\n";
for(int i=0;i<20;i++){
if((1<<i)&goup)cn=n[cn]->p[i];
}
return n[cn]->c;
}
