#include"bits/stdc++.h"
//#include"scrivener.h"
#define overload(a,b,c,d,...) d
#define rep1(a) for(ll _=0;_<(ll)a;++_)
#define rep2(i,a) for(ll i=0;i<(ll)(a);++i)
#define rep3(i,a,b) for(ll i=(ll)(a);i<(ll)(b);++i)
#define rep(...) overload(__VA_ARGS__,rep3,rep2,rep1)(__VA_ARGS__)
#define rrep1(i,a) for(ll i=(ll)(a)-1;i>=0;--i)
#define rrep2(i,a,b) for(ll i=(ll)(b)-1;i>=(ll)(a);--i)
#define rrep(...) overload(__VA_ARGS__,rrep2,rrep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
using namespace std;
using ll=long long;
using ull=unsigned long long;
using i128=__int128_t;
using ld=long double;
using vi=vector<int>;
using vl=vector<ll>;
template<typename T,typename U>inline bool chmin(T&a,const U&b){return (a>b?a=b,true:false);}
template<typename T,typename U>inline bool chmax(T&a,const U&b){return (a<b?a=b,true:false);}
struct PersistentArray{
struct Node{
int val;
Node*ch[2]={};
};
Node*root;
PersistentArray(){}
PersistentArray(vector<int>&a){
build(a);
}
Node*get_root(){return root;}
void destructive_set(Node*&nd,int idx,int val){
if(!nd)nd=new Node();
if(idx==0)nd->val=val;
else destructive_set(nd->ch[idx&1],idx>>1,val);
}
void build(const vector<int>&a){
for(int i=0;i<(int)a.size();++i){
destructive_set(root,i,a[i]);
}
}
Node*set(Node*const&nd,int idx,int val){
Node*ret=new Node();
if(nd){
memcpy(ret->ch,nd->ch,sizeof(nd->ch));
ret->val=nd->val;
}
if(idx==0){
ret->val=val;
}
else ret->ch[idx&1]=set(ret->ch[idx&1],idx>>1,val);
return ret;
}
int get(Node*const&nd,int idx)const{
if(!nd)return -1;
if(idx==0)return nd->val;
return get(nd->ch[idx&1],idx>>1);
}
};
PersistentArray a;
vector<pair<int,PersistentArray::Node*>>st;
using Node=PersistentArray::Node;
void Init() {
a=PersistentArray();
st.eb(0,a.get_root());
}
void TypeLetter(char L) {
//cerr<<"Type Letter "<<L<<endl;
int sz=st.back().first;
Node*nd=st.back().second;
st.emplace_back(sz+1,a.set(nd,sz,L-'a'));
}
void UndoCommands(int U) {
//cerr<<"Undo Commands "<<U<<endl;
assert(st.size()>=U);
st.emplace_back(st[st.size()-1-U]);
}
char GetLetter(int P) {
//cerr<<"Get Letter "<<P<<endl;
return 'a'+a.get(st.back().second,P);
}
