#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;
int SZ = 25;
struct Node{
char c = '.';
int dis = 0;
vector<int> anc;
Node(){
anc.resize(SZ);
}
};
vector<Node> tr;
vector<int> his;
int ts = 1;
void Init(){
tr.resize(1000005);
tr[0].dis = -1;
his.eb(0);
}
int newnode(int pr, char c){
int id = ts++;
tr[id].c = c;
tr[id].dis = tr[pr].dis + 1;
tr[id].anc[0] = pr;
for(int i = 1; i < SZ; i++){
tr[id].anc[i] = tr[tr[id].anc[i - 1]].anc[i - 1];
}
return id;
}
int jump(int id, int dis){
for(int i = 0; i < SZ; i++){
if(1 << i & dis) id = tr[id].anc[i];
}
return id;
}
void TypeLetter(char L){
int id = his.back();
id = newnode(id, L);
his.eb(id);
}
void UndoCommands(int U){
int id = his[(int)his.size() - U - 1];
his.eb(id);
}
char GetLetter(int P){
int now = his.back();
int dis = tr[now].dis - P;
now = jump(now, dis);
return tr[now].c;
}
