#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
const int lg=20;
int at=0;
const int MX=1e6+7;
vector<vector<int>> dp(lg,vector<int> (MX,0));
vector<char> c(MX);
vector<int> prof(MX);
void calc(int aux){
dp[0][at]=aux;
L(i,1,lg-1){
dp[i][at]=dp[i-1][dp[i-1][at]];
}
}
void Init() {
prof[0]=-1;
c[at]='x';
at++;
}
void TypeLetter(char L) {
c[at]=L;
prof[at]=prof[at-1]+1;
calc(at-1);
at++;
}
void UndoCommands(int U) {
auto id=at-U-1;
c[at]=c[id];
prof[at]=prof[id];
dp[at]=dp[id];
at++;
}
char GetLetter(int P) {
int id=at-1;
int d=prof[id]-P;
L(i,0,lg-1){
if((1<<i)&d)id=dp[i][id];
}
return c[id];
}
