#include<bits/stdc++.h>
using namespace std;
#define pb push_back
struct node{
char c;
int p[20];
int h;
};
vector<node> trie;
node make(int par, char ch){
node ret;
ret.c=ch;
ret.h=trie[par].h+1;
ret.p[0]=par;
for(int i=1; i<20; i++){
ret.p[i]=trie[ret.p[i-1]].p[i-1];
}
return ret;
}
int cur=0;
const int N = 1000010;
int curs[N];
int cnt;
void Add(char c){
curs[cnt]=trie.size();
trie.pb(make(cur, c));
cur=curs[cnt];
cnt++;
}
char lift(int v, int to){
int ret=v;
for(int i=19; i>=0; i--){
if(trie[trie[ret].p[i]].h >= to){
ret=trie[ret].p[i];
}
}
return trie[ret].c;
}
void TypeLetter(char c) {
Add(c);
}
void UndoCommands(int num) {
curs[cnt]=curs[cnt-1-num];
cur=curs[cnt];
cnt++;
}
char GetLetter(int ind) {
return lift(cur, ind+1);
}
void Init() {
node first;
first.h=0;
for(int i=0; i<20; i++)first.p[i]=0;
first.c=0;
trie.pb(first);
curs[0]=0;
cnt=1;
}
