#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
using namespace std;
const int lg = 20;
const int N = 1<<lg;
struct {
int anc[lg];
int len;
char l;
} node[N];
int pos = 0;
void Init() {}
void TypeLetter(char L) {
int v = pos+1;
node[v].anc[0] = pos;
Loop (i,1,lg)
node[v].anc[i] = node[node[v].anc[i-1]].anc[i-1];
node[v].len = node[pos].len+1;
node[v].l = L;
++pos;
}
void UndoCommands(int U) {
memcpy(&node[pos+1], &node[pos-U], sizeof(*node));
++pos;
}
char GetLetter(int P) {
//string s;
//for (int v = pos; node[v].l; v = node[v].anc[0])
// s += node[v].l;
//reverse(s.begin(), s.end());
//cout << s << '\n';
P = node[pos].len - 1 - P;
int v = pos;
LoopR (i,0,lg) {
if (!(P & (1<<i)))
continue;
v = node[v].anc[i];
}
return node[v].l;
}
