#include <bits/stdc++.h>
using namespace std;
const int mx = 1e6 + 5;
const int lg = 20;
int C[mx], I[mx];
char X[mx];
int p[lg][mx];
int n;
void show(int i){
printf("C : %d I : %d X : %c\n",C[i],I[i],X[C[i]]);
}
void Init() {
}
void TypeLetter(char L) {
++n;
I[n] = I[n-1] + 1;
C[n] = n;
X[n] = L;
p[0][n] = n - 1;
for(int j = 1; j < lg; j++){
//if(!p[j-1][n]) break;
//else{
p[j][n] = p[j-1][p[j-1][n]];
//}
}
}
void UndoCommands(int U) {
++n;
if(U == n){
I[n] = 0;
C[n] = 0;
X[n] = 'U';
return;
}
I[n] = I[n - 1 - U];
C[n] = C[n - 1 - U];
p[0][n] = n - 1 - U;
for(int j = 1; j < lg; j++){
//if(!p[j-1][n]) break;
//else{
p[j][n] = p[j-1][p[j-1][n]];
//}
}
}
char GetLetter(int P) {
++P;
int b = n;
for(int j = lg-1; j >= 0; j--){
if(I[b] == P) return X[C[b]];
if(I[p[j][b]] >= P) b = p[j][b];
}
return I[b] == P ? X[C[b]] : X[C[p[0][b]]];
}
