/* Arthur Conmy / arthurconmy */
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
#define REP(i,a,b) \
for(int i=(a); i<=(b); i++)
#define REPb(i,a,b) \
for(int i=(a); i>=(b); i--)
int p2[20];
int parent[20][1000001];
char letter_pres[1000001];
int cur_len[1000001];
int cur=0;
// vector<int> history;
void Init()
{
REP(i,0,19)
{
parent[0][i]=-1;
}
p2[0]=1;
REP(i,1,19)
{
p2[i]=p2[i-1]+p2[i-1];
}
}
void TypeLetter(char L)
{
parent[0][cur+1]=cur;
cur++;
letter_pres[cur]=L;
cur_len[cur]=cur_len[cur-1]+1;
REP(i,1,19)
{
parent[i][cur] = parent[i-1][parent[i-1][cur]];
}
}
void UndoCommands(int U)
{
int v_copying = cur - U;
cur++;
REP(i,0,19)
{
parent[i][cur] = parent[i][v_copying];
}
letter_pres[cur]=letter_pres[v_copying]; // could get iffy - unitialised char ???
cur_len[cur]=cur_len[v_copying];
}
char GetLetter(int P)
{
int length = cur_len[cur];
P++; // not zero-indexed anymore
int v=cur;
int up_trav = length-P;
REPb(i,19,0)
{
if(up_trav >= p2[i])
{
v=parent[i][v];
up_trav-=p2[i];
}
}
#ifdef ARTHUR_LOCAL
cout << letter_pres[v] << endl;
#endif
return letter_pres[v];
}
// int main()
// {
// #ifdef ARTHUR_LOCAL
// ifstream cin("input.txt");
// #endif
// Init();
// TypeLetter('a');
// TypeLetter('b');
// GetLetter(1);
// TypeLetter('d');
// UndoCommands(2);
// UndoCommands(1);
// GetLetter(2);
// TypeLetter('e');
// UndoCommands(1);
// UndoCommands(5);
// TypeLetter('c');
// GetLetter(2);
// UndoCommands(2);
// GetLetter(2);
// }
