#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
char op[MAXN];
int node[MAXN], depth[MAXN];
int dp[20][MAXN];
int cnt, cur;
void Init(){
depth[0] = 0;
cnt = cur = 0;
}
void TypeLetter(char l){
cnt ++;
dp[0][cnt] = cur; // meu pai eh o anterior
depth[cnt] = depth[cur] + 1;
op[cnt] = l;
node[cur + 1] = cnt;
cur = cnt;
for(int k=1; k<20; k++) dp[k][cnt] = dp[k - 1][dp[k - 1][cnt]];
}
void UndoCommands(int u){
cnt ++;
node[cnt] = node[cnt - u - 1];
cur = node[cnt]; // agora o no subiu
}
char GetLetter(int p){
int x = cur; // qual eh o cnt atual?
for(int k=19; k>=0; k--){
if(depth[dp[k][x]] > p){
x = dp[k][x];
}
}
return op[x];
}
