// And you curse yourself for things you never done
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 10, mod = 1e9 + 7, inf = 1e9 + 10;
int h[maxn], sp[20][maxn];
int nxt[maxn][26];
int point[maxn];
int nw, C;
void Init(){
memset(nxt, 0, sizeof nxt);
nw = C = 0;
}
void TypeLetter(char c){
if(nxt[point[nw]][c - 'a'] == 0){
nxt[point[nw]][c - 'a'] = ++C;
int pr = point[nw];
h[C] = h[pr] + 1;
sp[0][C] = pr;
for(int i = 1; i < 20; i++)
sp[i][C] = sp[i-1][sp[i-1][C]];
}
nw++;
point[nw] = nxt[point[nw-1]][c - 'a'];
}
void UndoCommands(int U){
nw++;
point[nw] = point[nw - 1 - U];
}
char GetLetter(int p){
int u = point[nw];
++p;
p = h[u] - p;
for(int i = 0; i < 20; i++)
if(bit(p, i))
u = sp[i][u];
for(int i = 0; i < 26; i++){
if(nxt[ sp[0][u] ][i] == u){
return 'a' + i;
}
}
assert(0);
}
