//雪花飄飄北風嘯嘯
//天地一片蒼茫
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int trie[1000005][26];
int par[1000005][22];
int d[1000005];
char letter[1000005];
int curr=0;
vector<int> pos;
int idx=1;
void Init() {
memset(trie,-1,sizeof(trie));
memset(par,-1,sizeof(par));
pos.push_back(curr);
}
void TypeLetter(char L) {
int nxt=L-'a';
if (trie[curr][nxt]==-1){
trie[curr][nxt]=idx;
d[idx]=d[curr]+1;
int pp=par[idx][0]=curr;
rep(x,0,22){
if (par[pp][x]==-1) break;
pp=par[idx][x+1]=par[pp][x];
}
letter[idx]=L;
idx++;
}
curr=trie[curr][nxt];
pos.push_back(curr);
}
void UndoCommands(int U) {
curr=pos[sz(pos)-U-1];
pos.push_back(curr);
}
char GetLetter(int p) {
//for (auto &it:pos) cout<<it<<" "; cout<<endl;
p=d[curr]-p-1;
int pp=curr;
rep(x,22,0) if (p&(1<<x)){
pp=par[pp][x];
}
//cout<<curr<<" "<<pp<<endl;
return letter[pp];
}
