#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
struct Node{
char val;
int dep;
vi nxt;
vi anc;
Node(char _val, int _dep): val(_val), dep(_dep), nxt(vi(26, 0)), anc(vi(20, 0)) {}
};
vector<Node> trie;
vi pos;
int ptr;
void Init(){
trie.pb(Node('$', -1));
pos.pb(0);
ptr = 0;
}
void TypeLetter(char L){
int& ch = trie[ptr].nxt[L - 'a'];
if(ch == 0){
ch = szof(trie);
trie.pb(Node(L, trie[ptr].dep + 1));
//cerr<<"new "<<ch<<" '"<<L<<"'"<<endl;
}
trie[ch].anc[0] = ptr;
FOR(j, 1, 19, 1){
trie[ch].anc[j] = trie[ trie[ch].anc[j-1] ].anc[j-1];
}
ptr = ch;
pos.pb(ptr);
//cerr<<"ptr = "<<ptr<<endl;
}
void UndoCommands(int U){
int id = pos[szof(pos) - 1 - U];
ptr = id;
pos.pb(ptr);
//cerr<<"ptr = "<<ptr<<endl;
}
char GetLetter(int P){
int dis = trie[ptr].dep - P;
int ret_node = ptr;
FOR(j, 0, 19, 1){
if(dis & (1<<j)) ret_node = trie[ret_node].anc[j];
}
char ret = trie[ret_node].val;
return ret;
}
