#include <bits/stdc++.h>
//#include "grader.h"
using namespace std;
typedef long long ll;
typedef long double ld;
int cur=0;
int pos[1000005];
char letter[1000005];
int qnum=0;
int depth[1000005];
int nxt[1000005][26];
int koji[1000005];
int par[1000005][25];
int tri=0;
void trieadd(char ch){
if(nxt[cur][ch-'a']){
cur = nxt[cur][ch-'a'];
return;
}
nxt[cur][ch-'a'] = ++tri;
depth[tri] = depth[cur]+1;
letter[tri] = ch;
par[tri][0] = cur;
cur = tri;
for(int i=1; i<=19; i++){
if(par[cur][i-1] == -1) continue;
par[cur][i] = par[par[cur][i-1]][i-1];
}
}
int findpar(int v, int k){
int cnt=0;
while(k){
if(k & 1) v = par[v][cnt];
cnt++;
k >>= 1;
}
return v;
}
void Init(){
for(int i=0; i<=1000000; i++){
for(int k=0; k<=20; k++){
par[i][k] = -1;
}
}
return;
}
void TypeLetter(char L) {
qnum++;
trieadd(L);
koji[qnum] = cur;
}
void UndoCommands(int U) {
qnum++;
cur = koji[qnum-U-1];
koji[qnum] = cur;
}
char GetLetter(int P) {
int x = findpar(cur, depth[cur]-P-1);
return letter[x];
}
