#include <bits/stdc++.h>
using namespace std;
int par[1000005][20];
int arr[1000005];
char ans[1000005];
int d[1000005];
int ptr=0;
void Init() {
//binary lifting
memset(par,-1,sizeof(par));
}
void TypeLetter(char L) {
ptr++;
arr[ptr]=ptr;
ans[ptr]=L;
par[ptr][0]=arr[ptr-1];
d[ptr]=d[arr[ptr-1]]+1;
//binary lifting
for(int x=1;x<20;x++){
if(par[ptr][x-1]==-1) continue;
par[ptr][x]=par[par[ptr][x-1]][x-1];
}
}
void UndoCommands(int U) {
ptr++;
arr[ptr]=arr[ptr-U-1];
}
char GetLetter(int P) {
//binary lifting
int diff=d[arr[ptr]]-P-1;
int target=arr[ptr];
for(int x=0;x<20;x++){
if(diff&(1<<x)){
target=par[target][x];
}
}
return ans[target];
}
