#include <bits/stdc++.h>
using namespace std;
int timer;
const int N = 1e6 + 2;
int lift[20][N], len[N];
char last[N];
void Init() {
timer = 0;
}
void TypeLetter(char l) {
timer++;
lift[0][timer] = timer - 1;
for (int i = 1; i < 20; i++){
lift[i][timer] = lift[i - 1][lift[i - 1][timer]];
}
last[timer] = l;
len[timer] = len[timer - 1] + 1;
}
void UndoCommands(int u) {
int ok = timer - u;
timer++;
len[timer] = len[ok];
last[timer] = last[ok];
for (int i = 0; i < 20; i++) lift[i][timer] = lift[i][ok];
}
char GetLetter(int p) {
p++;
int ok = timer;
for (int i = 19; i >= 0; i--){
int x = lift[i][ok];
if (len[x] < p) continue;
ok = x;
}
return last[ok];
}
