#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
using namespace std;
const int MxN=1e6+1, L=21;
int bin[MxN][L], con[MxN], cur, com_id, tree_id;
char val[MxN];
void build(int id)
{
FOR(i, 1, L) bin[id][i]=bin[bin[id][i-1]][i-1];
}
int lift(int id, int d)
{
FOR(i, 0, L) if(d&(1<<i))
{
id=bin[id][i];
}
return id;
}
void Init() {}
void TypeLetter(char l) {
int node=con[cur]; if(cur==0) node=tree_id+1;
bin[++tree_id][0]=node;
con[++com_id]=tree_id;
val[tree_id]=l;
build(tree_id);
}
void UndoCommands(int u) {
assert(com_id-u>=1);
con[com_id+1]=con[com_id-u];
com_id++;
}
char GetLetter(int p) {
int node=lift(con[com_id], p);
// cout << "Answer node: " << node << '\n';
return val[node];
}
