#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e6+10;
int zap[N],jump[N][21],dep[N];
char zn[N];
int l=1,num;
void Init(){
zap[0]=1;
for(int i=0;i<=20;i++) jump[1][i]=1;
}
void TypeLetter(char a){
jump[++l][0]=zap[num];
for(int i=1;i<=20;i++) jump[l][i]=jump[jump[l][i-1]][i-1];
dep[l]=dep[zap[num]]+1;
zn[l]=a,zap[++num]=l;
}
void UndoCommands(int x){
num++;
zap[num]=zap[num-x-1];
}
char GetLetter(int p){
p++;
int a=zap[num];
for(int i=20;i>=0;i--)
if(dep[jump[a][i]]>=p) a=jump[a][i];
return zn[a];
}
