#include <vector>
struct Edge{
int from;
char ch;
};
int allnode = 0;
int const NMAX = 1e6;
int jump[21][1 + NMAX];
int siz[1 + NMAX];
Edge parent[1 + NMAX];
void buildJump(int node) {
jump[0][node] = parent[node].from;
for(int k = 1;k <= 20;k++) {
jump[k][node] = jump[k-1][jump[k-1][node]];
}
}
void Init() {
// WARIOWARE !!!
}
void TypeLetter(char L) {
allnode++;
parent[allnode] = {allnode-1, L};
siz[allnode] = siz[allnode-1] + 1;
buildJump(allnode);
}
void UndoCommands(int U) {
int from = allnode - U;
allnode++;
parent[allnode] = {from, 0};
siz[allnode] = siz[from];
buildJump(allnode);
}
int cautbin(int node, int len) {
for(int k = 20;k >= 0;k--) {
int temp = jump[k][node];
if(siz[temp] >= len) {
node = temp;
}
}
return node;
}
char GetLetter(int P) {
int tempNode = cautbin(allnode, P+1);
return parent[tempNode].ch;
}
