#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class Node {
public:
Node* ptrs[20]; // Jump Pointers
char v;
Node(char a_v, Node* par): v(a_v) {
if(par == nullptr) return;
update_par(par);
}
void construct_jump_ptrs() {
for(int i = 1; i < 20; i++) {
ptrs[i] = ptrs[i - 1]->ptrs[i - 1];
}
}
void update_par(Node* par) {
ptrs[0] = par;
construct_jump_ptrs();
}
char at(int i, int size) {
int actual_ind = size - i - 1;
Node* cur_ptr = this;
for(int j = 0; j < 20; j++) {
if((actual_ind >> j) & 0b1) cur_ptr = cur_ptr->ptrs[j];
}
return cur_ptr->v;
}
};
vector<Node*> hist;
vector<int> sizes;
int last_version_ind = -1;
void Init() {
hist.reserve(1000001);
sizes.reserve(1000001);
Node* first = new Node('L', nullptr);
first->update_par(first);
hist.push_back(first);
sizes.push_back(0);
last_version_ind++;
}
void TypeLetter(char L) {
sizes.push_back(sizes[last_version_ind] + 1);
hist.push_back(new Node(L, hist[last_version_ind]));
last_version_ind++;
}
void UndoCommands(int U) {
sizes.push_back(sizes[last_version_ind - U]);
hist.push_back(hist[last_version_ind - U]);
last_version_ind++;
}
char GetLetter(int P) {
return hist[last_version_ind]->at(P, sizes[last_version_ind]);
}
