// In the name of Allah
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define X real()
#define Y imag()
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e6 + 7;
const int maxlg = 20;
int sz; pii p[maxn];
int h[maxn], up[maxn][maxlg];
char A[maxn];
void Init() {
sz = 1;
}
void TypeLetter(char ch) {
int v = sz++;
A[v] = ch; p[v] = Mp(v - 1, 1);
h[v] = h[p[v].F] + p[v].S;
up[v][0] = v;
for (int i = 1; i < maxlg; i++) {
int u = p[up[v][i - 1]].F;
up[v][i] = up[u][i - 1];
}
}
void UndoCommands(int x) {
int v = sz++;
A[v] = '.'; p[v] = Mp(v - x - 1, 0);
h[v] = h[p[v].F] + p[v].S;
up[v][0] = up[p[v].F][0];
for (int i = 1; i < maxlg; i++) {
int u = p[up[v][i - 1]].F;
up[v][i] = up[u][i - 1];
}
}
char GetLetter(int x) {
int v = sz - 1; x = (h[v] - x);
while (x > 0) {
int j = __builtin_ctz(x);
v = up[v][j]; x ^= (1 << j);
if (x != 0) v = p[v].F;
}
return A[v];
}
