#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+50;
char last;
struct node{
char c;
int up[21],sz;
node(){
c = 0;
sz = 0;
memset(up,-1,sizeof(up));
}
}v[maxn];
int cur;
void Init(){}
void TypeLetter(char L) {
cur++;
v[cur].c = L;
v[cur].up[0] = cur-1;
v[cur].sz = v[cur-1].sz + 1;
int tmp = cur-1;
for(int i=1;i<20;i++){
if(tmp == -1)break;
v[cur].up[i] = v[tmp].up[i-1];
tmp = v[tmp].up[i-1];
}
}
void UndoCommands(int U) {
cur++;
v[cur] = v[cur-U-1];
}
char GetLetter(int P) {
int m = v[cur].sz - P - 1;
int tmp = cur;
for(int i=20;i>=0;i--){
if((m>>i) & 1)tmp = v[tmp].up[i];
}
return v[tmp].c;
}
