#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2000005;
const int LOG = 20;
vector<char> v;
vector<int> parent;
vector<int> sz;
vector<int> mp;
vector<vector<int>> up;
int cur = 0;
void Init() {
v.assign(1, 0);
parent.assign(1, -1);
sz.assign(1, 0);
mp.assign(1, 0);
up.assign(1, vector<int>(LOG, -1));
cur = 0;
}
void TypeLetter(char L) {
int new_version = v.size();
v.push_back(L);
parent.push_back(cur);
sz.push_back(sz[cur] + 1);
up.push_back(vector<int>(LOG, -1));
up[new_version][0] = parent[new_version];
for (int j = 1; j < LOG; ++j)
if (up[new_version][j-1] != -1)
up[new_version][j] = up[up[new_version][j-1]][j-1];
mp.push_back(new_version);
cur = new_version;
}
void UndoCommands(int U) {
int undo = mp[mp.size() - 1 - U];
mp.push_back(undo);
cur = undo;
}
char GetLetter(int P) {
int now = cur;
int need = sz[now] - 1 - P;
for (int j = LOG - 1; j >= 0; --j) {
if (need >= (1 << j) && now != -1) {
now = up[now][j];
need -= (1 << j);
}
}
return v[now];
}
