#include <iostream>
const int N = 1000005;
using namespace std;
typedef long long ll;
int cur;
struct Node
{
Node* par1;
Node* par2;
int h;
char c;
Node(char c)
{
par1 = nullptr;
par2 = nullptr;
h = -1;
this->c = c;
}
Node(Node* par, char c)
{
par1 = par;
h = par->h + 1;
int dist1 = par->par2->h - par->h;
int dist2 = par->par2->par2->h - par->par2->h;
if (dist1 == dist2)
{
par2 = par->par2->par2;
} else
{
par2 = par;
}
this->c = c;
}
};
Node* nodes[N];
char getKth(int i, Node* node)
{
if (node->h == i) return node->c;
if (node->par2->h >= i) return getKth(i, node->par2);
return getKth(i, node->par1);
}
void Init()
{
nodes[0] = new Node(' ');
nodes[0]->par1 = nodes[0];
nodes[0]->par2 = nodes[0];
nodes[0]->h = -1;
cur = 0;
}
void TypeLetter(char L) {
cur++;
nodes[cur] = new Node(nodes[cur - 1], L);
}
void UndoCommands(int U) {
nodes[cur + 1] = nodes[cur - U];
cur++;
}
char GetLetter(int P) {
char c = getKth(P, nodes[cur]);
return c;
}
