#include<bits/stdc++.h>
using namespace std;
#define taskname "A"
#define pb push_back
#define mp make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;
const int maxn = 1e6 + 5;
const int logn = log2(maxn) + 1;
template<class T = char>
struct node{
node* pre[logn];
T val;
int len;
node(){
// cout << 1;
for(int j = 0 ; j < logn ; ++j)pre[j] = 0;
len = 0;
}
void add(node* par , T val){
len = par->len + 1;
this->val = val;
pre[0] = par;
// cout << pre[0] << endl;
for(int j = 1 ; j < logn ; ++j){
if(pre[j - 1])pre[j] = pre[j - 1]->pre[j - 1];
else break;
}
}
T GetValAt(int pos){
pos = len - pos - 1;
node* now = this;
// cout << now << endl;
for(int j = 0 ; j < logn ; ++j){
if((pos >> j) & 1)now = now->pre[j];
}
// cout << now << endl;
return now->val;
}
};
node<char> preorder[maxn];
node<char>* a[maxn];
int now = 0;
void Init() {
for(int i = 0 ; i < maxn ; ++i)a[i] = &preorder[i];
}
void TypeLetter(char L) {
++now;
a[now]->add(a[now - 1] , L);
}
void UndoCommands(int U) {
++now;
a[now] = a[now - U - 1];
}
char GetLetter(int P) {
return a[now]->GetValAt(P);
}
