#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2000005;
vector<char> v;
vector<int> parent;
vector<int> sz;
vector<int> mp;
int cur = 0;
void Init() {
v.assign(1, 0);
parent.assign(1, -1);
sz.assign(1, 0);
mp.assign(1, 0);
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);
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;
while (now != 0) {
if (need == 0)
return v[now];
now = parent[now];
need--;
}
return ' ';
}
