#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll lim=1e6+5;
struct node{
char c;
node *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,nullptr);
}
void TypeLetter(char L) {
n[cur]=new node();
n[cur]->d=n[cur-1]->d+1;
n[cur]->c=L;
n[cur]->p[0]=n[cur-1];
for(int i=1;i<20;i++){
if(n[cur]->p[i-1]==nullptr)break;
n[cur]->p[i]=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;
node* cn=n[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=cn->p[i];
}
return cn->c;
}
