# include <bits/stdc++.h>
using namespace std;
char last;
vector <char> t;
vector <int> pos;
vector <int> par;
stack <char> st;
vector <array <int,20> > lca;
vector <int> H;
bool fl = false;
int prevv=-1, ver=-1;
vector <char> w;
void Init() {
prevv = -1;
ver = -1;
t.clear();
pos.clear();
par.clear();
//st.clear();
fl = false;
}
array <int,20> p;
void create_lca(int v)
{
int i;
p[0] = par[v];
for(i=1;i<20;i++)
{
if(p[i-1]==-1)p[i] = -1;
else
p[i] = lca[p[i-1]][i-1];
}
lca.push_back(p);
}
void TypeLetter(char L) {
last = L;
if(prevv==-1)H.push_back(0);
else
H.push_back(H[prevv]+1);
ver++;
pos.push_back(ver);
t.push_back(L);
par.push_back(prevv);
create_lca(ver);
prevv = ver;
}
void UndoCommands(int U) {
int k = pos[pos.size()-U-1];
pos.push_back(k);
prevv = k;
}
char GetLetter(int P) {
/* if(!fl)
{
for(int i = prevv; i!=-1; i =par[i])
{
st.push(t[i]);
}
while(!st.empty())
{
w.push_back(st.top());
st.pop();
}
fl= true;
}
return w[P];*/
int h = P;
int i, cur = prevv;
for(i=19;i>=0;i--)
{
//cout<<cur<<" "<<H[cur]<<" "<<lca[cur][i]<<endl;
if(lca[cur][i]!=-1&&H[lca[cur][i]]>=h)cur = lca[cur][i];
}
return t[cur];
//return last;
}
