//Challenge: Accepted
#include <bits/stdc++.h>
using namespace std;
#ifdef zisk
void debug(){cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary(T l, T r){
while (l != r) cout << *l << " ", l++;
cout << endl;
}
#else
#define debug(...) 0
#define pary(...) 0
#endif
#define ll long long
#define maxn 1000005
#define pii pair<int, int>
#define ff first
#define ss second
int pos[maxn], len[maxn], anc[20][maxn];
char c[maxn];
int ti = 1, st = 0;
void Init() {}
void TypeLetter(char L) {
int prv = pos[ti-1];
st++;
anc[0][st] = prv;
for (int i = 1;i < 20;i++) anc[i][st] = anc[i-1][anc[i-1][st]];
len[ti] = len[ti-1] + 1;
pos[ti] = st;
c[st] = L;
ti++;
}
void UndoCommands(int U) {
pos[ti] = pos[ti - U - 1];
len[ti] = len[ti - U - 1];
ti++;
}
char GetLetter(int P) {
int dis = len[ti-1] - P - 1;
int cur = pos[ti-1], cnt = 0;
while (dis) {
if (dis & 1) cur = anc[cnt][cur];
cnt++, dis >>= 1;
}
return c[cur];
}
