#include <bits/stdc++.h>
#define pb push_back
using namespace std;
#define debug(args) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }
const int L = 20;
struct node {
int len;
char c;
int pos, anc[L];
node(int id) {
len = 0, pos = 0;
for (int i = 0; i < L; i++)
anc[i] = id;
}
node() {}
};
vector <node> arr;
void Init() {
arr.pb(node(0));
}
void TypeLetter(char C) {
int sze = arr.size();
node now;
now.len = arr[sze-1].len + 1;
now.c = C;
now.pos = sze;
now.anc[0] = arr[sze-1].pos;
for (int i = 1; i < L; i++) {
now.anc[i] = arr[now.anc[i-1]].anc[i-1];
}
arr.pb(now);
}
void UndoCommands(int U) {
int sze = arr.size();
node now = arr[sze-1-U];
arr.pb(now);
}
char GetLetter(int P) {
int pos = arr[arr.size()-1].pos;
int jump = arr[pos].len - P - 1;
for (int i = 0; i < L; i++) {
if (jump & (1<<i)) {
pos = arr[pos].anc[i];
}
}
return arr[pos].c;
}
