#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 1e6;
const int MAX_LOG = 20;
int sz = 0;
int up[MAXN][MAX_LOG + 1];
int len[MAXN];
char s[MAXN];
void Init() {}
void TypeLetter(char L) {
s[sz] = L;
len[sz] = 1;
if (sz > 0) len[sz] += len[sz - 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[sz] = s[idx];
len[sz] = len[idx];
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];
}
