#include <vector>
using namespace std;
int node = 0;
int lastnode = 0;
//vector<pair<int,char> > g[1000010];
int dp[23][1000010];
vector<int> curnode;
char chr[1000100];
int depth[1000100];
void Init() {
dp[0][0] = -1;
curnode.push_back(0);
return;
}
void TypeLetter(char L) {
node++;
//g[lastnode].push_back(make_pair(node,L));
dp[0][node] = lastnode;
for(int k=1; k<=22; k++) {
if(dp[k-1][node] == -1)
dp[k][node] = -1;
else
dp[k][node] = dp[k-1][dp[k-1][node]];
}
chr[node] = L;
depth[node] = depth[lastnode] + 1;
curnode.push_back(node);
lastnode = node;
}
void UndoCommands(int U) {
int tmpnode = curnode[curnode.size()-U-1];
lastnode = tmpnode;
curnode.push_back(lastnode);
}
char GetLetter(int P) {
int u = lastnode;
P++;
for(int i=22; i>=0; i--) {
if(depth[u]-(1<<i) >= P) {
u = dp[i][u];
}
}
return chr[u];
}
