#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define pb push_back
#define ll long long
#define ui uint64_t
#define ar array
#define us unordered_set
#define cont(set, element) ((set).find(element) != (set).end())
/********* DEBUG *********/
template <typename T>
void outvec(const vector<T>& Z){
for (const T& x : Z)
cout << x << ' ';
cout << "\n";
}
void printVariable(const any& var) {
if (!var.has_value()) {
cout << "null";
return;
}
if (var.type() == typeid(int)) {
cout << any_cast<int>(var);
} else if (var.type() == typeid(double)) {
cout << any_cast<double>(var);
} else if (var.type() == typeid(float)) {
cout << any_cast<float>(var);
} else if (var.type() == typeid(char)) {
cout << any_cast<char>(var);
} else if (var.type() == typeid(bool)) {
cout << (any_cast<bool>(var) ? "true" : "false");
} else if (var.type() == typeid(string)) {
cout << any_cast<string>(var);
} else if (var.type() == typeid(const char*)) {
cout << any_cast<const char*>(var);
} else if (var.type() == typeid(long long)) {
cout << any_cast<long long>(var);
} else {
cout << "[unknown type]";
}
}
template<typename... Args>
void outval(Args... args) {
vector<any> variables = {args...};
for (size_t i = 0; i < variables.size(); ++i) {
printVariable(variables[i]);
if (i != variables.size() - 1) {
cout << " ";
}
}
cout << "\n";
}
#define nl "\n"
#define sp << " " <<
/********* DEBUG *********/
const ll MOD = 1000000007;
const ll MOD2 = 998244353;
const ll MOD3 = 1000000000;
const ll needMOD = 987654321;
const ll mxN = 1000005;
const ll inf = 1e18;
/*
create trie, for each letter create new node, for undo commands go back U states,
for getletter find P'th ancestor of current node, do it quick using binlift
*/
ll curridx, depth[mxN], jump[mxN][21];
char chars[mxN];
vector<ll> state;
void Init(){
memset(depth, 0, sizeof(depth));
memset(jump, 0, sizeof(jump));
memset(chars, 0, sizeof(chars));
curridx = 0;
state.pb(0);
}
void TypeLetter(char L){
curridx++;
chars[curridx] = L;
ll currstate = state.back();
depth[curridx] = depth[currstate] + 1;
jump[curridx][0] = currstate;
for (int i = 1; i <= 20; i++){
jump[curridx][i] = jump[ jump[curridx][i-1] ][i-1];
}
state.pb(curridx);
}
void UndoCommands(int U){
state.pb(state[sz(state)-U-1]);
}
char GetLetter(int P){
ll currstate = state.back();
ll steps = depth[currstate] - P - 1;
//outval("steps:",steps);
for (int i = 0; i < 21; i++){
if (steps & (1 << i)){
currstate = jump[currstate][i];
}
}
return chars[currstate];
}
