#include <vector>
#include <map>
using namespace std;
map<char, int> trie[1000001]; int prv[1000001][20];
int node,now,time,hist[1000001],len[1000001]; char last[10000001];
void Init() {}
void TypeLetter(char L) {
int &n = trie[now][L];
if (n == 0){
n = ++node;
prv[n][0] = now;
for (int i=1;i<20;i++) prv[n][i] = prv[prv[n][i-1]][i-1];
len[n] = len[now] + 1;
last[n] = L;
}
hist[++time] = now = n;
}
void UndoCommands(int U) {
now = hist[time-U];
hist[++time] = now;
}
char GetLetter(int P) {
int x = now; P = len[x] - P - 1;
for (int i=0;i<20;i++) if (P & (1 << i)) x = prv[x][i];
return last[x];
}
