#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
#define N 1000009
#define l 25
struct val
{
char c;
int ref, dist;
};
int pos = 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[pos];
v[pos+1] = {L, pos, last.dist+1};
pos++;
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)
{
int par = pos-U;
val x = v[par];
pos++;
v[pos] = x;
anc[pos] = anc[par];
}
char GetLetter(int P) {
int livcurr = v[pos].dist;
int steps = livcurr - P - 1;
if(steps==0) return v[pos].c;
int sol = pos;
for(int i=0; i<l; i++) if( steps & (1<<i) ) sol = anc[sol][i];
return v[sol].c;
}
