#include<bits/stdc++.h>
using namespace std;
int operations;
char lastchar[1000005];
int P[1000005][20],sz[1000005];
void Init() {}
void TypeLetter(char L){
operations++;
P[operations][0] = operations - 1;
sz[operations] = sz[operations - 1] + 1;
for (int i = 1; i < 20; i ++)
P[operations][i] = P[ P[operations][i-1] ][i-1];
lastchar[operations] = L;
}
void UndoCommands(int U) {
operations++;
sz[operations] = sz[operations - 1 - U];
P[operations][0] = P[operations - 1 - U][0];
lastchar[operations]= lastchar[operations - 1 - U];
for (int i = 1; i < 20; i++)
P[operations][i] = P[ P[operations][i-1] ][i-1];
}
char GetLetter(int p) {
int x = sz[operations] - p - 1;
int cur = operations;
for (int i = 0; i < 20 ;i++) {
if (x & (1 << i)) {
cur = P[cur][i];
}
}
return lastchar[cur];
}
