#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;
int cnt = 1;
const int nmax = 1000001;
int a[nmax][20];
char c[nmax];
int depth[nmax];
int last[nmax];
int cur = 0;
void Init() {
}
void TypeLetter(char L) {
a[cnt][0] = last[cur];
depth[cnt] = depth[last[cur]] + 1;
for(int j = 1; j < 20; j++)
a[cnt][j] = a[a[cnt][j - 1]][j - 1];
last[cur + 1] = cnt;
c[cnt] = L;
cnt++;
cur++;
}
void UndoCommands(int U) {
cur++;
last[cur] = last[cur - U - 1];
// cout << depth[last[cur]];
}
char GetLetter(int P) {
int x = depth[last[cur]];
// cout << x << ' ';
int o = x - P - 1;
int cc = last[cur];
while(o){
int t = log2(o);
cc = a[cc][t];
o -= (1 << t);
}
return c[cc];
}
