#include <bits/stdc++.h>
using namespace std;
int sz = 0, max_log = 21;
vector<int> len;
vector< vector<int> > up;
string s;
void Init() {}
void TypeLetter(char L) {
s.push_back(L);
if (len.empty()) len.push_back(1);
else len.push_back(len.back() + 1);
up.push_back(vector<int>(max_log + 1));
if (sz == 0) up[0][0] = 0;
else up[sz][0] = sz - 1;
for (int i = 1; i <= max_log; i++) up[sz][i] = up[up[sz][i - 1]][i - 1];
sz++;
}
void UndoCommands(int U) {
int idx = sz - U - 1;
s.push_back(s[idx]);
len.push_back(len[idx]);
up.push_back(vector<int>(max_log + 1));
up[sz][0] = up[idx][0];
for (int i = 1; i <= max_log; i++) up[sz][i] = up[up[sz][i - 1]][i - 1];
sz++;
}
char GetLetter(int P) {
P = len[sz - 1] - P - 1;
int cur = sz - 1;
for (int i = 0; i <= max_log; i++) if (P & (1 << i)) cur = up[cur][i];
return s[cur];
}
