//#include "grader.cpp"
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 1e6 + 5;
const long long onlyOnes = (1LL<<61) - 1;
long long mask1, mask2, mask3;
struct SegmentTree
{
int nodes = 0;
long long tree[MAXN*25];
//0-24|25-49|50-55
SegmentTree()
{
memset(this->tree, 0, sizeof(this->tree));
}
int getNode()
{
nodes++;
return nodes - 1;
}
void encodeNum(long long &x, long long num, int lBit, int rBit)
{
for(int bit = lBit;bit<=rBit;bit++)
{
x &= (onlyOnes - (1LL<<bit));
x |= ((num>>(bit-lBit)&1LL)<<bit);
}
}
long long readNum(long long x, int type)
{
if(type==1) return (x&mask1);
if(type==2) return ((x&mask2)>>25);
if(type==3) return ((x&mask3)>>50);
}
void build(int node, int l, int r)
{
if(l==r) return;
int L = getNode();
int R = getNode();
encodeNum(tree[node], L, 0, 24);
encodeNum(tree[node], R, 25, 49);
build(L, l, (l+r)/2);
build(R, (l+r)/2+1, r);
}
void update(int q, int node, char c, int l, int r, int other)
{
if(l==r)
{
encodeNum(tree[node], c-'a', 50, 55);
return;
}
int L;
if(l<=q && q<=(l+r)/2)
{
L = getNode();
update(q, L, c, l, (l+r)/2, readNum(tree[other], 1));
}
else
{
L = readNum(tree[other], 1);
}
encodeNum(tree[node], L, 0, 24);
int R;
if((l+r)/2+1<=q && q<=r)
{
R = getNode();
update(q, R, c, (l+r)/2+1, r, readNum(tree[other], 2));
}
else
{
R = readNum(tree[other], 2);
}
encodeNum(tree[node], R, 25, 49);
}
char getChar(int q, int node, int l, int r)
{
if(l==r) return char(readNum(tree[node], 3)+'a');
if(l<=q && q<=(l+r)/2) return getChar(q, readNum(tree[node], 1), l, (l+r)/2);
return getChar(q, readNum(tree[node], 2), (l+r)/2+1, r);
}
};
struct String
{
int sz;
int root;
String(){}
String(int sz)
{
this->sz = sz;
}
};
SegmentTree *T = new SegmentTree();
int COMMAND = 0;
String state[MAXN];
void Init()
{
mask1 = 0;
for(int bit = 0;bit<=24;bit++) mask1 += (1LL<<bit);
mask2 = 0;
for(int bit = 25;bit<=49;bit++) mask2 += (1LL<<bit);
mask3 = 0;
for(int bit = 50;bit<=55;bit++) mask3 += (1LL<<bit);
state[0] = String(0);
state[0].root = T->getNode();
T->build(state[0].root, 0, MAXN);
}
void TypeLetter(char L)
{
COMMAND++;
state[COMMAND].sz = state[COMMAND-1].sz + 1;
state[COMMAND].root = T->getNode();
T->update(state[COMMAND].sz-1, state[COMMAND].root, L, 0, MAXN, state[COMMAND-1].root);
}
void UndoCommands(int U)
{
COMMAND++;
state[COMMAND] = state[COMMAND-1-U];
}
char GetLetter(int P)
{
return T->getChar(P, state[COMMAND].root, 0, MAXN);
}
