#include<bits/stdc++.h>
using namespace std;
vector<char> C;
vector<int> D[30];//parentesco de tal é tal
vector<int> TS;
int a=0, b=0;
void Init() {}
void TypeLetter(char L) {
C.push_back(L);
if(a==0){
a=1;
for(int i=0;i<25;i++){
D[i].push_back(-1);
}
}else{
if(C[b-1]=='X'){
D[0].push_back(D[0][b-1]);
}else{
D[0].push_back(b-1);
}
for(int i=1;i<25;i++){
D[i].push_back(D[i-1][D[i-1].back()]);
}
TS.push_back(TS[b-1]+1);
}
b++;
}
void UndoCommands(int U) {
C.push_back('X');
if(C[b-U-1]=='X'){
D[0].push_back(D[0][b-U-1]);
}else{
D[0].push_back(b-U-1);
}
for(int i=1;i<25;i++){
D[i].push_back(D[i-1][D[i-1].back()]);
}
TS.push_back(TS[b-U-1]);
b++;
}
char GetLetter(int P) {
int g=TS[b-1]-P+1, h=b-1;
if(C[b-1]!='X'){
g--;
}
int F=0;
while(g>0){
if(g%2==1){
h=D[F][h];
}
g/=2;
F++;
}
return C[h];
}
