#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
const int logg=22;
int trie[maxn][26];
int lift[maxn][logg];
char slovo[maxn];
bool uradio[maxn];
int gde[maxn];
int trengde=0;
int koliko=1;
void probaj(int poz,int prosli){
if(uradio[poz]) return;
lift[poz][0]=prosli;
for(int i=1;i<logg;i++){
lift[poz][i]=lift[lift[poz][i-1]][i-1];
}
uradio[poz]=true;
}
int dalje(int poz,int a){
if(trie[poz][a]==0) trie[poz][a]=koliko++;
probaj(trie[poz][a],poz);
return trie[poz][a];
}
int koji(){
int pom=gde[trengde];
int ret=0;
for(int i=logg-1;i>=0;i--){
if(lift[pom][i]==0) continue;
pom=lift[pom][i];
ret+=(1<<i);
}
return ret;
}
int skoci(int x){
int wtf=gde[trengde];
for(int i=logg-1;i>=0;i--){
if((1<<i)>x) continue;
x-=(1<<i);
wtf=lift[wtf][i];
}
return wtf;
}
void Init(){
probaj(0,0);
}
void TypeLetter(char L) {
gde[trengde+1]=dalje(gde[trengde],L-'a');
trengde++;
slovo[gde[trengde]]=L;
}
void UndoCommands(int U) {
gde[trengde+1]=gde[trengde-U];
trengde++;
}
char GetLetter(int P) {
return slovo[skoci(koji()-P)];
}
/*
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
*/
