#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
#define MAXL 25//max logN
int up[MAXL][MAXN];
vector<int> ver_node;
int trie[MAXN][26];
char let[MAXN];//letter
int len[MAXN];//length of word
int max_node;
void Init() {
ver_node.push_back(0);//fake root
}
void TypeLetter(char L) {
int curr=ver_node.back();
if(trie[curr][L-'a']==0){
max_node++;
trie[curr][L-'a']=max_node;
ver_node.push_back(max_node);
let[max_node]=L;
len[max_node]=len[curr]+1;
up[0][max_node]=curr;
for(int i=1;i<MAXL;i++){
up[i][max_node]=up[i-1][up[i-1][max_node]];
}
}else{
ver_node.push_back(trie[curr][L-'a']);
}
}
void UndoCommands(int U) {
int temp=ver_node[(ver_node.size()-1)-U];
ver_node.push_back(temp);
}
char GetLetter(int P) {
int curr=ver_node.back();
int num=len[curr]-P-1;
for(int i=0;i<MAXL;i++,num>>=1){
if(num&1){
curr=up[i][curr];
}
}
return let[curr];
}
