#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
int ind[1000001];
int back[1000001];
int st[1000001];
int cc[1000001];
int co=1;
int cur[1000001][20];
char cop[1000001];
/*int find(int no){
if(st[no]==1){
return no;
}
par[no]=find(par[no]);
return no;
}*/
void Init() {
/*for(int j=0;j<20;j++){
cur[j][0]=-1;
}*/
//memset(cur,-1,sizeof(cur));
}
void TypeLetter(char L) {
cop[co]=L;
if(co>0){
ind[co]=back[co-1];
cc[co]=1+cc[ind[co]];
cur[co][0]=ind[co];
for(int j=1;j<20;j++){
if(cur[co][j-1]==-1){
break;
}
cur[co][j]=cur[cur[co][j-1]][j-1];
}
}
else{
cc[co]=1;
}
back[co]=co;
co+=1;
}
void UndoCommands(int u) {
back[co]=back[co-u-1];
//cout<<co<<","<<back[co-u]<<endl;
co+=1;
}
char GetLetter(int p) {
int la=back[co-1];
if(p==cc[la]-1){
// cout<<cop[la]<<endl;
return cop[la];
}
int jj=la;
int x=cc[la]-p-1;
for(int j=19;j>=0;j--){
if((x&(1<<j))){
jj=cur[jj][j];
}
}
//cout<<cop[jj]<<endl;
return cop[jj];
}
/*
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
*/
/*
g++ -DEVAL -Wall -static -O2 -o aa grader1.cpp scrivener.cpp
*/
