#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, nodes, cur;
void Init(){
depth[0] = 0;
cnt = cur = 0;
}
void TypeLetter(char l){
cnt ++; nodes ++; // adiciona uma node
depth[nodes] = depth[cur] + 1; // o pai dessa node eh o cur
op[nodes] = l;
node[cnt] = nodes; // qual eh o no que o cnt representa?
dp[0][nodes] = cur;
for(int k=1; k<20; k++) dp[k][nodes] = dp[k - 1][dp[k - 1][nodes]];
cur = nodes;
}
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? (cur = node[cnt])
for(int k=19; k>=0; k--){
if(depth[dp[k][x]] > p){
x = dp[k][x];
}
}
return op[x];
}
