#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3;
struct node {
node* L;
node* R;
char c;
int cnt = 0;
void apply(node* x) {
L = x->L;
R = x->R;
c = x->c;
cnt = x->cnt;
}
};
node* s[N];
int n = 0;
struct segtree {
void build(node*& R, int l, int r) {
R = new node{};
if (l == r) {
return ;
}
int mid = l + r >> 1;
build(R->L, l, mid);
build(R->R, mid + 1, r);
}
node* modify(node* R, int l, int r, int pos, char c) {
node* res = new node{};
if (l == r) {
res->c = c;
res->cnt = 1;
return res;
}
res->L = R->L;
res->R = R->R;
int mid = l + r >> 1;
if (pos <= mid) res->L = modify(R->L, l, mid, pos, c);
else res->R = modify(R->R, mid + 1, r, pos, c);
res->cnt = res->L->cnt + res->R->cnt;
return res;
}
char get(node* R, int l, int r, int pos) {
if (l == r) return R->c;
int mid = l + r >> 1;
if (pos <= mid) return get(R->L, l, mid, pos);
return get(R->R, mid + 1, r, pos);
}
};
segtree Tree;
string st[N];
void Init() {
s[0] = new node{};
Tree.build(s[0], 0, N - 1);
}
void TypeLetter(char L) {
++n;
s[n] = Tree.modify(s[n - 1], 0, N - 1, s[n - 1]->cnt, L);
}
void UndoCommands(int m) {
++n;
s[n] = new node{};
s[n]->apply(s[n - m - 1]);
}
char GetLetter(int p) {
return Tree.get(s[n], 0, N - 1, p);
}
