/**
* Author: Nicholas Winschel
* Created: 06.04.2023 10:21:03
**/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())
struct node {
int h=0; char c='.';
array<node *, 22> jmp;
node () {
for (int i = 0; i < 22; i++) {
jmp[i]=this;
}
}
node (node *par, char _c) : c(_c) {
jmp[0]=par;
// cerr << "dbg: " << jmp[0]->c << endl;
// cerr << "0\n";
// cerr << jmp[0] << "\n";
h=par->h + 1;
for (int i = 1; i < 22; i++) {
// cerr << i << endl;
jmp[i]=jmp[i-1]->jmp[i-1];
// cout << jmp[i] << endl;
// cerr << jmp[i]->c << endl;
}
}
char get(int p) {
int ab = h-p-1;
node *cur = this;
for (int i = 0; i < 22; i++) if (ab&(1<<i)) cur = cur->jmp[i];
return cur->c;
}
};
V<node*> roots;
char last;
void Init() {
roots.push_back(new node);
}
void TypeLetter(char L) {
// cerr << "T " << L << " " << roots[sz(roots)-1]->c << endl;
roots.push_back(new node(roots[sz(roots)-1], L));
}
void UndoCommands(int U) {
// cerr << "U " << U << endl;
roots.push_back(roots[sz(roots)-1-U]);
}
char GetLetter(int P) {
// cerr << "P " << P << endl;
return roots[sz(roots)-1]->get(P);
}
