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