#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e6 + 10;
const int lg = 20;
int n, cur, h[maxn], idx[maxn], par[maxn][lg];
string s;
void Init() {
memset(par, -1, sizeof par);
idx[0] = -1;
}
void TypeLetter(char L){
s.push_back(L);
int v = s.size()-1;
if (idx[n] == -1){
h[v] = 0;
}
else{
h[v] = h[idx[n]] + 1;
}
par[v][0] = idx[n];
for (int i = 1; i < lg; i++){
if (par[v][i-1] != -1) par[v][i] = par[par[v][i-1]][i-1];
}
n++;
idx[n] = v;
}
void UndoCommands(int U) {
idx[n+1] = idx[n-U];
n++;
}
char GetLetter(int P) {
int v = idx[n];
int x = h[v] - P;
for (int i = 0; i < lg; i++) if ((x >> i) & 1) v = par[v][i];
return s[v];
}
