#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 3e2;
int prv[N], id[N], len[N];
int commands = 0, up[N][22];
char ch[N];
void Init() {
}
void TypeLetter(char L) {
commands++;
id[commands] = commands;
prv[commands] = max(1, id[commands - 1]);
ch[commands] = L;
len[commands] = len[prv[commands - 1]] + 1;
up[commands][0] = prv[commands];
for (int i = 1; i < 22; i++){
up[commands][i] = up[up[commands][i - 1]][i - 1];
}
//cout << "\t" << commands << ' ' << L << endl;
}
void UndoCommands(int U) {
commands++;
id[commands] = id[commands - U - 1];
len[commands] = len[commands - U - 1];
}
char GetLetter(int P) {
P++;
int x = id[commands];
for (int i = 21; i >= 0; i--){
if (len[up[x][i]] >= P) x = up[x][i];
}
return ch[x];
}
/**
14
T a
T b
P 1
T d
U 2
U 1
P 2
T e
U 1
U 5
T c
P 2
U 2
P 2
5
T a
U 1
U 1
U 2
P 0
*/
