#include <bits//stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_multiset;
#define ll long long
#define iloop(m, h) for (auto i = m; i != h; i += (m < h ? 1 : -1))
#define jloop(m, h) for (auto j = m; j != h; j += (m < h ? 1 : -1))
#define kloop(m, h) for (auto k = m; k != h; k += (m < h ? 1 : -1))
#define lloop(m, h) for (auto l = m; l != h; l += (m < h ? 1 : -1))
#define pll pair<ll, ll>
#define INF 1000000000000000
#define MOD1 1000000007
#define MOD2 998244353
#define MOD3 1000000009
int twok[20][1000005], tc[1000005];
char qu[1000005];
ll cn = 0;
void Init() {
memset(twok, -1, sizeof(twok));
}
void TypeLetter(char L) {
twok[0][cn] = cn-1;
tc[cn] = (twok[0][cn] != -1 ? tc[twok[0][cn]] : 0) + 1;
iloop(1, 20) {
if (twok[i-1][cn] == -1) continue;
twok[i][cn] = twok[i-1][twok[i-1][cn]];
}
qu[cn] = L;
cn++;
}
void UndoCommands(int U) {
twok[0][cn] = cn-U-1;
tc[cn] = (twok[0][cn] != -1 ? tc[twok[0][cn]] : 0);
iloop(1, 20) {
if (twok[i-1][cn] == -1) continue;
twok[i][cn] = twok[i-1][twok[i-1][cn]];
}
cn++;
}
char GetLetter(int P) {
P++;
ll ci = cn - 1;
iloop(19, -1) if (twok[i][ci] != -1 && tc[twok[i][ci]] >= P) ci = twok[i][ci];
return qu[ci];
}
