#include <bits/stdc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;
const int INF = 1e9 + 7, N = 1e6 + 7;
char t[N];
int p[N][20], d[N];
int cnt = 1;
vi his({0});
void Init() {
}
void TypeLetter(char c) {
int u = his.back();
int v = cnt++;
t[v] = c, d[v] = d[u] + 1;
p[v][0] = u;
for(int i = 1; i < 20; i++)
p[v][i] = p[p[v][i - 1]][i - 1];
his.PB(v);
}
void UndoCommands(int k) {
his.PB(his[SZ(his) - k - 1]);
}
char GetLetter(int k) {
int u = his.back();
int step = d[u] - 1 - k;
for(int i = 0; i < 20; i++)
if(step >> i & 1)
u = p[u][i];
return t[u];
}
