#include <bits/stdc++.h>
#define LOG 22
#define MAX 1000010
using namespace std;
class PersistentStack
{
public:
void add(char s)
{
curNode++;
curVersion++;
curTop = curNode;
v[curNode] = s;
version[curVersion] = curNode;
dp[0][curNode] = version[curVersion - 1];
prof[curNode] = prof[ dp[0][curNode] ] + 1;
for(int k = 1 ; k < LOG ; k++)
{
int jump = dp[k - 1][curNode];
dp[k][curNode] = dp[k - 1][jump];
}
}
void back(int k)
{
curVersion++;
version[curVersion] = version[curVersion - k - 1];
curTop = version[ curVersion ];
}
char query(int k)
{
int d = prof[curTop] - k;
int cur = curTop;
for(int g = 0 ; g < LOG ; g++)
if(d & (1 << g)) cur = dp[g][cur];
return v[cur];
}
private:
int curTop;
int curNode;
int curVersion;
int prof[MAX];
int dp[LOG][MAX];
int version[MAX];
char v[MAX];
};
PersistentStack p;
void Init() { }
void TypeLetter(char L) { p.add( L ); }
void UndoCommands(int U) { p.back( U ); }
char GetLetter(int P) { return p.query( P + 1 ); }
