#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+25;
int curop,sz;
char arr[MAXN];
int ops[MAXN],par[MAXN][20],dep[MAXN];
void Init(){
curop = 1;
sz = 1;
ops[curop] = 1;
dep[sz] = 0;
for(int i = 1;i<20;++i){
par[1][i] = 1;
}
}
void TypeLetter(char L){
curop++; sz++;
ops[curop] = sz;
arr[sz] = L;
dep[sz] = dep[ops[curop-1]]+1;
par[sz][0] = ops[curop-1];
for(int i = 1;i<20;++i){
par[sz][i] = par[par[sz][i-1]][i-1];
}
}
void UndoCommands(int U){
curop++;
ops[curop] = ops[curop-U-1];
}
char GetLetter(int P){
P++; int cur = ops[curop];
int d = dep[cur]-P;
for(int i = 0;i<20;++i){
if((d >> i)&1){
cur = par[cur][i];
}
}
return arr[cur];
}
