#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7, LG=20;
int ile[LIM], nxt[LIM][LG], sum[LIM][LG], akt;
char V[LIM];
void licz() {
for(int i=1; i<LG; ++i) {
nxt[akt][i]=nxt[nxt[akt][i-1]][i-1];
sum[akt][i]=sum[akt][i-1]+sum[nxt[akt][i-1]][i-1];
}
}
void Init() {}
void TypeLetter(char x) {
++akt;
V[akt]=x;
ile[akt]=ile[akt-1]+1;
nxt[akt][0]=akt-1;
sum[akt][0]=1;
licz();
}
void UndoCommands(int x) {
++akt;
ile[akt]=ile[akt-x-1];
nxt[akt][0]=akt-x-1;
licz();
}
char GetLetter(int x) {
x=ile[akt]-x-1;
int p=akt;
for(int i=LG-1; i>=0; --i) if(sum[p][i]<=x) {
x-=sum[p][i];
p=nxt[p][i];
}
return V[p];
}
