#include <bits/stdc++.h>
using namespace std;
#define N 1000009
#define l 25
struct val
{
char c;
int ref, dist;
};
int ultimo = 0;
vector<vector<int>> anc(N, vector<int> (l));
vector<val> v(N);
void Init()
{
v[0] = {'$', 0, 0};
for(int i=0; i<l; i++) anc[0][i] = 0;
}
void TypeLetter(char L)
{
val last = v[ultimo];
v[ultimo+1] = {L, ultimo, last.dist+1};
ultimo++;
int pos = ultimo;
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[ultimo-U];
ultimo++;
v[ultimo] = x;
int pos = ultimo;
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 = ultimo;
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;
}
