#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
const int N=1e6+5,lg=21;
int par[N][lg],d[N],pos[N];
char ch[N];
int cur=0,dep=0,now=0,com=0;
void Init(){
return;
}
void TypeLetter(char L){
cur++;
com++;
pos[com]=cur;
ch[cur]=L;
par[cur][0]=now;
now=cur;
dep++;
d[now]=dep;
int k=2,l=1;
while(k<=dep){
par[cur][l]=par[par[cur][l-1]][l-1];
l++;
k*=2;
}
return;
}
void UndoCommands(int U){
U=pos[com-U];
com++;
pos[com]=U;
now=U;
dep=d[U];
return;
}
char GetLetter(int P){
int up=d[now]-P-1;
int r=now;
for(int i=20;i>=0;i--){
if(up&(1<<i)){
r=par[r][i];
}
}
return ch[r];
}
