#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
const int K=21;
const int N=1e6+55;
int jump[N][K];
char z[N];
int dp[N];
void Init() {dp[0]=0;}
int op=0;
void TypeLetter(char c) {
++op;
z[op]=c;
jump[op][0]=op;
dp[op]=dp[op-1]+1;
jump[op][1]=jump[op-1][0];
for (int i=2; i<K; ++i) {
jump[op][i]=jump[jump[op][i-1]][i-1];
}
}
void UndoCommands(int x) {
++op;
dp[op]=dp[op-x-1];
jump[op][0]=jump[op-x-1][0];
jump[op][1]=jump[op-x-1][1];
for (int i=2; i<K; ++i) {
jump[op][i]=jump[jump[op][i-1]][i-1];
}
}
char GetLetter(int p) {
int n=dp[op];
int u=jump[op][0];
int x=n-1-p;
for (int i=K-1; i>0; --i) {
if (x&(1<<(i-1))); else continue;
u=jump[u][i];
}
return z[u];
}
