#include <bits/stdc++.h>
using namespace std;
struct node {
int lpt, rpt;
};
const int maxn = 1e6, maxN = 4e6 + 10;
vector<node> seg[maxN];
vector<char> leaf[maxn+5];
vector<int> sz = {0};
void build(int id, int l, int r) {
seg[id] = {{0, 0}};
if (l==r) {
leaf[l] = {'.'};
return;
}
int mid = (l+r)/2;
build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int pt, int l, int r, int target, char val) {
if (l==r) {
leaf[l].push_back(val);
seg[id].push_back({0, 0});
return;
}
int mid = (l+r)/2;
seg[id].push_back(seg[id][pt]);
if (l<=target && target<=mid) {
update(id*2, seg[id][pt].lpt, l, mid, target, val);
seg[id].back().lpt = (int)seg[id*2].size() - 1;
} else {
update(id*2+1, seg[id][pt].rpt, mid+1, r, target, val);
seg[id].back().rpt = (int)seg[id*2+1].size() - 1;
}
}
char qry(int id, int pt, int l, int r, int target) {
if (r<target || target<l) return '.';
if (l==r) return leaf[l][pt];
int mid = (l+r)/2;
return max(qry(id*2, seg[id][pt].lpt, l, mid, target), qry(id*2+1, seg[id][pt].rpt, mid+1, r, target));
}
void Init() {
build(1, 0, maxn);
}
void TypeLetter(char L) {
update(1, (int)seg[1].size()-1, 0, maxn, sz.back(), L);
sz.push_back(sz.back() + 1);
}
void UndoCommands(int U) {
seg[1].push_back(seg[1][(int)seg[1].size() - U - 1]);
sz.push_back(sz[(int)sz.size() - U - 1]);
}
char GetLetter(int P) {
return qry(1, (int)seg[1].size() - 1, 0, maxn, P);
}
