#include <bits/stdc++.h> using namespace std; char last; vector <char> t; int cur = 0; int up[22][1000005]; int d[1000005]; int node[1000005]; int curnode; void Init() {t.emplace_back(' ');} void TypeLetter(char L) { cur++; int prev = node[cur-1]; curnode++; up[cur][0] = prev; t.emplace_back(L); d[curnode] = d[prev] + 1; for (int i = 1; i <= 20; i++) { up[cur][i] = up[up[cur][i-1]][i-1]; } node[cur] = curnode; } void UndoCommands(int U) { cur++; node[cur] = node[cur - U - 1]; } char GetLetter(int P) { int now = node[cur]; P = d[now]-P-1; for (int i = 20; i >= 0; i--) { if (P >= (1<<i)) { cur = up[now][i]; P -= (1<<i); } } return t[now]; }