/*
what we can do is store the ending after each "operation" in a trie.
then, undo becomes "go back k+1 endings". this can be done with binary jumping
something like that
fuck it we vibe code ts
*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fastIO cin.tie(0); ios::sync_with_stdio(false)
int endptr[1000005];
char letters[1000005];
int jump[1000005][25]; // log_2(1e6) = 20 (the size of log still impresses me to this day)
int depth[1000005];
int i = -1;
int opCnt = -1;
void Init() {
// who even needs to initialize jack bro
// nvm
memset(jump, -1, sizeof(jump));
}
void TypeLetter(char L) {
i++;
opCnt++;
if(opCnt != 0) {
depth[i] = depth[endptr[opCnt]] + 1;
jump[i][0] = endptr[opCnt]; // parent
for(int j = 1; (1ll << j) <= depth[i]; j++) {
jump[i][j] = jump[jump[i][j-1]][j-1];
}
} else {
depth[i] = 0;
}
letters[i] = L;
endptr[opCnt] = i;
}
void UndoCommands(int U) {
opCnt++;
endptr[opCnt] = endptr[opCnt - U];
}
char GetLetter(int P) {
// note that depth + 1 gives us the length, so to find how much we have to go from the back of the string, we have to traverse...
ll depthDiff = depth[endptr[opCnt]] - P;
int end = endptr[opCnt];
for(ll i = 22; i >= 0 && depthDiff > 0; i--) {
if(depthDiff & (1ll<<i)) {
end = jump[end][i];
depthDiff -= (1ll<<i);
}
}
return letters[end];
}
