#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
const int MAXK = 25;
const int MAXN = 1e6+100;
int cnt = 0;
int ch[MAXN][26];
char letter[MAXN];
int lift[MAXN][MAXK];
int dep[MAXN];
int initNode (char c) {
letter[cnt] = c;
FOR(i, 0, 25) ch[cnt][i] = -1;
cnt++;
return cnt-1;
}
void buildLift (int id) {
FOR(i, 1, MAXK-1)
lift[id][i] = lift[lift[id][i-1]][i-1];
}
int addNode (int id, char c) {
int letId = c-'a';
if (ch[id][letId] == -1) {
int chId = initNode(c);
ch[id][letId] = chId;
lift[chId][0] = id;
buildLift(chId);
dep[chId] = dep[id]+1;
}
return ch[id][letId];
}
int lft (int id, int d) {
FOR(i, 0, MAXK-1)
if (d & (1<<i))
id = lift[id][i];
return id;
}
int curId;
int timeToNode [MAXN];
void Init() {
curId = 0;
timeToNode[curId] = initNode('a');
dep[curId] = -1;
}
void TypeLetter(char L) {
timeToNode[curId+1] = addNode(timeToNode[curId], L);
curId++;
}
void UndoCommands(int U) {
timeToNode[curId+1] = timeToNode[curId-U];
curId++;
//printCur();
}
char GetLetter(int P) {
int nodeId = lft (timeToNode[curId], dep[timeToNode[curId]]-P);
return letter[nodeId];
}
