#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define sz(x) int((x).size())
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
template<class X, class Y>
inline bool maximize(X &x, const Y &y) {return (x < y ? x = y, 1 : 0);}
template<class X, class Y>
inline bool minimize(X &x, const Y &y) {return (x > y ? x = y, 1 : 0);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int Random(int l, int r) {
return uniform_int_distribution<int>(l, r)(rng);
}
const int MAXN = 1000006;
int lastLetter[MAXN], lenOf[MAXN], id[MAXN], P[MAXN][20], numQuery;
void Init(void) {
numQuery = 0;
lastLetter[0] = -1;
}
void TypeLetter(char c) {
++numQuery;
id[numQuery] = numQuery;
lenOf[numQuery] = lenOf[id[numQuery - 1]] + 1;
P[numQuery][0] = id[numQuery - 1];
for (int j = 1; j < 20; ++j)
P[numQuery][j] = P[P[numQuery][j - 1]][j - 1];
lastLetter[numQuery] = c;
}
void UndoCommands(int U) {
++numQuery;
id[numQuery] = id[numQuery - U - 1];
}
char GetLetter(int T) {
int x(id[numQuery]);
for (int i1 = lenOf[x] - T - 1; i1 > 0; i1 ^= i1 & -i1) {
int i = __builtin_ctz(i1 & -i1);
x = P[x][i];
}
return lastLetter[x];
}
