#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void Init() {}
int par[21][1000005], cur, dep[1000005];
char stuf[1000005];
void TypeLetter(char L) {
stuf[++cur] = L;
dep[cur] = dep[cur - 1] + 1;
par[0][cur] = cur - 1;
for(int i = 1; i <= 20; i++)par[i][cur] = par[i-1][par[i-1][cur]];
}
void UndoCommands(int U) {
cur++;
dep[cur] = dep[cur - U - 1];
stuf[cur] = stuf[cur - U - 1];
par[0][cur] = par[0][cur - U - 1];
for(int i = 1; i <= 20; i++)par[i][cur] = par[i-1][par[i-1][cur]];
}
char GetLetter(int P) {
int brr = dep[cur] - P - 1;
int tmp = cur;
for(int i = 20; i >= 0; i--)if(brr >> i & 1)tmp = par[i][tmp];
//cout << cur << ' ' << tmp << ' ' << dep[cur] << ' ' << '\n';
return stuf[tmp];
}
