#include <bits/stdc++.h>
using namespace std;
#define REP(i, a, b) for(int i = a; i < b; i++)
int par[1000069], kpar[1000069], h[1000069], cnt; char c[1000069];
void Init() {}
void TypeLetter(char L) {
cnt++;
par[cnt]=cnt-1;
c[cnt]=L;
h[cnt]=h[cnt-1]+1;
if(h[cnt-1]+h[kpar[kpar[cnt-1]]]==(h[kpar[cnt-1]]<<1)) kpar[cnt]=kpar[kpar[cnt-1]];
else kpar[cnt]=cnt-1;
}
void UndoCommands(int U) {
cnt++;
par[cnt]=par[cnt-U-1];
kpar[cnt]=kpar[cnt-U-1];
h[cnt]=h[cnt-U-1];
c[cnt]=c[cnt-U-1];
}
char GetLetter(int P) {
int cur=cnt;
while(h[cur]>P+1) {
if(kpar[cur]!=-1&&h[kpar[cur]]>=P+1) cur=kpar[cur];
else cur=par[cur];
}
return c[cur];
}
