#pragma GCC optimize ("O3")
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
struct node;
using node_ptr = node*;
struct node
{
int len;
char l;
vector<node_ptr> upread;
vector<node_ptr> upundo;
node()
{
upread = vector<node_ptr>(22);
upundo = vector<node_ptr>(22);
l = '0';
len = 0;
}
node(char il, node_ptr lr, node_ptr lu) : l(il)
{
upread.resize(22);
upundo.resize(22);
upread[0] = lr;
upundo[0] = lu;
len = lr->len + 1;
for (int i = 1; i < 22; i++)
{
upread[i] = (upread[i - 1] ? upread[i - 1]->upread[i - 1] : node_ptr());
upundo[i] = (upundo[i - 1] ? upundo[i - 1]->upundo[i - 1] : node_ptr());
}
}
node_ptr getundo(int k)
{
node_ptr cp = this;
for (int i = 21; i >= 0; i--)
{
if (k & (1ll<<i)) cp = cp->upundo[i];
assert(cp != 0);
}
return cp;
}
node_ptr getread(int k)
{
node_ptr cp = this;
for (int i = 21; i >= 0; i--)
{
if (k & (1ll<<i)) cp = cp->upread[i];
assert(cp != 0);
}
return cp;
}
};
node_ptr back;
void Init()
{
back = new node();
}
void TypeLetter(char L)
{
back = new node(L, back, back);
}
void UndoCommands(signed U)
{
node_ptr rep = back->getundo(U);
back = new node(rep->l, rep->upread[0], back);
}
char GetLetter(signed P)
{
int ind = back->len - 1 - P;
node_ptr rd = back->getread(ind);
return rd->l;
}
