#include <bits/stdc++.h>
#define forn(i, a, b) for(int i = int(a); i <= int(b); ++ i)
#define fora(i, a, b) for(int i = int(a); i >= int(b); -- i)
using namespace std;
const int maxn = 1e6;
const int log2maxn = log2(maxn);
struct ura{
int longitud;
char letra;
ura *ancestros[log2maxn + 1];
ura(){
longitud = 0;
letra = '0';
forn(i, 0, log2maxn){
ancestros[i] = nullptr;
}
}
};
ura *movimientos[maxn + 1];
int idx;
void Init() {
forn(i, 0, maxn){
movimientos[i] = nullptr;
}
movimientos[0] = new ura();
movimientos[0]->letra = '1';
idx = 1;
}
void TypeLetter(char L) {
ura *atras;
atras = movimientos[idx - 1];
if(atras->letra == '0'){
atras = atras->ancestros[0];
}
movimientos[idx] = new ura();
movimientos[idx]->letra = L;
movimientos[idx]->longitud = atras->longitud + 1;
movimientos[idx]->ancestros[0] = atras;
forn(i, 1, log2maxn){
if(atras->ancestros[i - 1] == nullptr){
break;
}
movimientos[idx]->ancestros[i] = atras->ancestros[i - 1];
atras = atras->ancestros[i - 1];
}
idx ++;
}
void UndoCommands(int U) {
ura *atras = movimientos[idx - U - 1];
movimientos[idx] = new ura();
if(atras->letra == '0'){
atras = atras->ancestros[0];
}
movimientos[idx]->ancestros[0] = atras;
idx ++;
}
char GetLetter(int P) {
ura *actual = movimientos[idx - 1];
if(actual->letra == '0'){
actual = actual->ancestros[0];
}
P = actual->longitud - P;
P --;
fora(i, log2maxn, 0){
if((P & (1 << i))){
actual = actual->ancestros[i];
}
}
return actual->letra;
}
