/*
______ _____ _______ _ _ _______ __ _ _____ _ _ _
|_____/ | | | |____/ |______ | \ | | | | | |
| \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__|
. . . . . .
_\/ \/_ _\/ \/_ _\/ \/_
_\/\/_ _\/\/_ _\/\/_
_\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_
/ /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \
_/\/\_ _/\/\_ _/\/\_
/\ /\ /\ /\ /\ /\
' ' ' ' ' '
*/
#pragma GCC optimize ("O3")
#pragma GCC target ("avx2")
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <climits>
#include <cstdint>
#include <cmath>
#include <chrono>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <vector>
using namespace std;
/*using ll = long long;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()
#define f first
#define s second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
*/
const int LOG=21;
const int MX=1e6+5;
struct no{
char c;
int pai[LOG];
int profundidade;
};
int tempo;
no vv[MX];
void imprimir(){
for(int i=0; i<tempo+1; i++){
cout<<"->"<<vv[i].c<<' '<<vv[i].pai[0]<<' ';
}
cout<<'\n';
}
void Init(){
tempo=0;
//raiz
vv[0].c='#';
for(int i=0; i<LOG; i++){
vv[0].pai[i]=0;
}
vv[0].profundidade=0;
//imprimir();
}
void TypeLetter(char L){
tempo++;
vv[tempo].c=L;
vv[tempo].pai[0]=tempo-1;
for(int i=1; i<LOG; i++){
vv[tempo].pai[i]=vv[vv[tempo].pai[i-1]].pai[i-1];
}
vv[tempo].profundidade=vv[tempo-1].profundidade+1;
//imprimir();
}
void UndoCommands(int U) {
tempo++;
vv[tempo]=vv[tempo-U-1];
//imprimir();
}
char GetLetter(int P) {
int x=vv[tempo].profundidade-P-1;
int pos=tempo;
for(int i=0; i<LOG; i++){
if(x&(1<<i)) pos=vv[pos].pai[i];
}
return vv[pos].c;
//imprimir();
}
