#include <bits/stdc++.h>
using namespace std;
#define N 1000001
int l;
struct val
{
char c;
int ref, dist;
};
vector<vector<int>> anc;
vector<val> v;
void Init()
{
v.push_back({'$', 0, 0});
l = 25;
anc.resize(N, vector<int> (l));
for(int i=0; i<l; i++) anc[0][i] = 0;
}
void TypeLetter(char L)
{
val last = v[v.size()-1];
v.push_back({L, int(v.size())-1, last.dist+1});
int pos = v.size()-1;
anc[pos][0] = v[pos].ref;
for(int i=1; i<l; i++) anc[pos][i] = anc[anc[pos][i-1]][i-1];
}
void UndoCommands(int U)
{
val x = v[v.size()-1-U];
v.push_back(x);
int pos = v.size()-1;
anc[pos][0] = v[pos].ref;
for(int i=1; i<l; i++) anc[pos][i] = anc[anc[pos][i-1]][i-1];
}
char GetLetter(int P) {
int curr = v.size()-1;
int livcurr = v[curr].dist;
int steps = livcurr - P - 1;
if(steps==0) return v[curr].c;
int sol = curr;
for(int i=0; i<l; i++) if( steps & (1<<i) ) sol = anc[sol][i];
return v[sol].c;
}
