#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 2e6 + 10;
char last;
int n;
char onv[maxn];
int from[maxn], jump[maxn][22], len[maxn];
vector < int > g;
int curr;
void Init()
{
n = 1;
onv[1] = '-';
len[1] = 0;
curr = 1;
g.pb(1);
}
void TypeLetter(char L) {
last = L;
n ++;
from[n] = curr;
onv[n] = L;
len[n] = len[curr] + 1;
jump[n][0] = curr;
for (int j = 1; j < 21; ++ j)
{
jump[n][j] = jump[jump[n][j-1]][j-1];
}
curr = n;
g.pb(curr);
}
void UndoCommands(int U)
{
int sz = g.size()-1;
curr = g[sz - U];
g.pb(curr);
}
char GetLetter(int P)
{
int state = curr;
int on = state;
int steps = len[state] - P - 1;
//cout << curr << " " << len[curr] << " " << P+1 << endl;
// if(!(len[state] >= P+1))cout << "????" << endl;
for (int bit = 0; bit < 21; ++ bit)
{
if((1 << bit) & steps)state = jump[state][bit];
}
return onv[state];
}
