#include<bits/stdc++.h>
using namespace std;
char curr[1000005];
int sparse[1000005][21];
int cntop;
int len[1000005];
void Init() {
cntop = 0;
}
void TypeLetter(char L) {
cntop++;
len[cntop] = len[cntop-1] + 1;
curr[cntop] = L;
sparse[cntop][0] = cntop-1;
for(int i=1; i<=20; i++) {
if(sparse[cntop][i-1] == 0) sparse[cntop][i-1] = 0;
else sparse[cntop][i] = sparse[sparse[cntop][i-1]][i-1];
}
}
void UndoCommands(int U) {
cntop++;
len[cntop] = len[cntop-U-1];
curr[cntop] = curr[cntop-U-1];
for(int i=0; i<=20; i++) sparse[cntop][i] = sparse[cntop-U-1][i];
}
char GetLetter(int P) {
P++;
int ptr = len[cntop], tmp = cntop;
for(int i=20; i>=0; i--) {
if(ptr - (1<<i) >= P) {
ptr -= (1<<i);
tmp = sparse[tmp][i];
}
}
return curr[tmp];
}
