#include <bits/stdc++.h>
using namespace std;
int idx[1000002], up[1000002][21], cnter = 0, cur = 0, lv[1000002];
char val[1000002];
void Init(){}
void TypeLetter(char L){
val[++cnter] = L; idx[cnter] = cnter;
up[cnter][0] = cur; lv[cnter] = lv[cur] + 1;
for(int i = 1; i <= 20; i++) up[cnter][i] = up[up[cnter][i - 1]][i - 1];
cur = cnter; val[cnter] = L;
}
void UndoCommands(int U){
cur -= U; idx[++cnter] = idx[cur];
up[cnter][0] = up[cur][0]; lv[cnter] = lv[cur];
for(int i = 1; i <= 20; i++) up[cnter][i] = up[up[cnter][i - 1]][i - 1];
cur = cnter;
}
char GetLetter(int P){
int find = lv[cur] - (P + 1); int u = cur;
for(int i = 20; i >= 0; i--){
if(find >= (1 << i)){
u = up[u][i]; find -= (1 << i);
}
}
return val[idx[u]];
}
