// Starcraft 2 enjoyer //
#include <bits/stdc++.h>
// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
using namespace std;
#define LSOne(X) ((X) & -(X))
const int N = 1e6 + 5;
const int K = 1e2 + 5;
const int M = 2e5 + 5;
const int LG = 21;
const long long INF = 1e18 + 5;
const int C = 26;
const int B = 1000;
const int MOD = 998244353;
int undoLift[LG][N], charLift[LG][N], id, cur, idcur[N], len[N], mxid, mxcur;
char val[N];
void addId()
{
mxid++;
undoLift[0][mxid] = id;
id = mxid;
for (int x = 1; x < LG; x++)
{
undoLift[x][id] = undoLift[x - 1][undoLift[x - 1][id]];
}
}
void addCur()
{
mxcur++;
charLift[0][mxcur] = cur;
len[mxcur] = len[cur] + 1;
cur = mxcur;
for (int x = 1; x < LG; x++)
{
charLift[x][cur] = charLift[x - 1][charLift[x - 1][cur]];
}
}
void TypeLetter(char c)
{
addId();
addCur();
val[cur] = c;
idcur[id] = cur;
}
void UndoCommands(int i)
{
int cid = id;
for (int x = 0; x < LG; x++)
{
if (i >> x & 1)
cid = undoLift[x][cid];
}
cur = idcur[cid];
addId();
idcur[id] = cur;
}
char GetLetter(int i)
{
i = len[cur] - i - 1;
// cout << len[cur] << "\n";
// cout << i << "\n";
int ccur = cur;
for (int x = 0; x < LG; x++)
{
if (i >> x & 1)
{
ccur = charLift[x][ccur];
}
}
return val[ccur];
}
void Init()
{
cur = id = 0;
}
