#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef vector<ii> vii;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define RE1(a,b) REP(a,1,b+1)
#define FOR(a,b) for(auto& a : b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), e.end()
const int MX = 1e6+10;
int pre[MX][20];
int head[MX], len[MX], current=0, nxt=0;
char last[MX];
int command=0;
void Init() {
current = nxt = 0;
head[0] = nxt;
len[0] = 0;
RE(i,20) pre[0][i] = 0;
nxt++;
}
void TypeLetter(char L) {
len[nxt] = len[current] + 1;
last[nxt] = L;
int x = current;
RE(i,20) {
pre[nxt][i] = x;
x = pre[x][i];
}
head[++command] = current = nxt++;
}
void UndoCommands(int U) {
command++;
head[command] = current = head[command - U - 1];
}
char GetLetter(int P) {
int dx = len[current] - P - 1;
int u = current;
RE(i,20) if(dx&(1<<i)) u = pre[u][i];
return last[u];
}
