#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int MAX = 1e6 + 15;
const int LOG = 21;
int dp[MAX][LOG], tam[MAX], cnt;
char letter[MAX];
void Init(){ }
void calcLift(int curNode){
for(int j = 1; j < LOG; j++)
dp[curNode][j] = dp[ dp[curNode][j - 1] ][j - 1];
}
void TypeLetter(char L){
int curNode = ++cnt;
letter[curNode] = L;
dp[curNode][0] = cnt - 1;
tam[curNode] = tam[cnt - 1] + 1;
calcLift(curNode);
}
void UndoCommands(int U){
int curNode = ++cnt;
dp[curNode][0] = cnt - 1 - U;
tam[curNode] = tam[dp[curNode][0]];
calcLift(curNode);
}
char GetLetter(int P){
int curNode = cnt; P++;
for(int j = LOG - 1; j >= 0; j--)
if(tam[ dp[curNode][j] ] >= P && dp[curNode][j] > 0)
curNode = dp[curNode][j];
return letter[curNode];
}
