//#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
const int DIM = 1e6 + 5;
pair <int, int> cur = {0, 0};
int tt[DIM][21];
int pref[DIM][21];
int nr1, nr2;
char ch[DIM];
int le[DIM], le2[DIM], tang[DIM];
int p2[25];
void Init() {
p2[0] = 1;
for (int i = 1; i <= 20 ; ++i)
p2[i] = p2[i - 1] * 2;
}
void TypeLetter(char L) {
++nr1; ++nr2;
le[nr1] = le[cur.first] + 1;
ch[nr1] = L;
pref[nr1][0] = cur.first;
for (int k = 1; p2[k] < le[nr1] ; ++k)
pref[nr1][k] = pref[pref[nr1][k - 1]][k - 1];
le2[nr2] = le2[cur.second] + 1;
tt[nr2][0] = cur.second;
for (int k = 1; p2[k] < le2[nr2] ; ++k)
tt[nr2][k] = tt[tt[nr2][k - 1]][k - 1];
cur = {nr1, nr2};
tang[nr2] = nr1;
}
void UndoCommands(int U) {
++nr2;
pair <int, int> aux = cur;
for (int k = 0; U > 0 ; ++k) {
if (p2[k] & U) {
cur.second = tt[cur.second][k];
U = U ^ p2[k];
}
}
cur = {tang[cur.second], nr2};
tang[nr2] = cur.first;
le2[cur.second] = le2[aux.second] + 1;
tt[cur.second][0] = aux.second;
for (int k = 1; p2[k] < le2[cur.second] ; ++k)
tt[cur.second][k] = tt[tt[cur.second][k - 1]][k - 1];
}
char GetLetter(int P) {
++P;
int dif = le[cur.first] - P;
int ind = cur.first;
for (int k = 0; dif > 0 ; ++k) {
if (p2[k] & dif) {
ind = pref[ind][k];
dif = dif ^ p2[k];
}
}
return ch[ind];
}
