#include <bits/stdc++.h>
using namespace std;
#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;
const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;
const int N = 1e6 + 5;
const int LOG = 21;
void Init() {}
int x = 0;
int op[N], sm[N], lca[LOG][N];
void TypeLetter(char c) {
op[++x] = c;
sm[x] = sm[x - 1] + 1;
lca[0][x] = x - 1;
for(int i = 1; i < LOG; i++) {
lca[i][x] = lca[i - 1][lca[i - 1][x]];
}
}
void UndoCommands(int k) {
x++;
sm[x] = sm[x - 1 - k];
lca[0][x] = x - 1 - k;
for(int i = 1; i < LOG; i++) {
lca[i][x] = lca[i - 1][lca[i - 1][x]];
}
}
char GetLetter(int p) {
int x1 = x;
for(int i = LOG - 1; i >= 0; i--) {
if(sm[lca[i][x1]] >= p + 1) {
x1 = lca[i][x1];
}
}
return op[x1];
}
