#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll ancestor[1000002][25];
ll currletter[1000002];
ll length[1000002];
ll plen = 0, pt = 0;
void Init()
{
}
void TypeLetter(char L)
{
plen+=1;
pt=plen-1;
currletter[plen] = L;
length[plen] = length[pt]+1;
ancestor[plen][0] = pt;
for(int i=1;i<=24;i++)
{
ancestor[plen][i] = ancestor[ancestor[plen][i-1]][i-1];
}
}
void UndoCommands(int U)
{
plen+=1;
pt=plen-U-1;
currletter[plen]=currletter[pt];
length[plen]=length[pt];
for(int i=0;i<=24;i++)
{
ancestor[plen][i]=ancestor[pt][i];
}
}
char GetLetter(int P)
{
P+=1;
ll k;
k=length[plen]-P;
pt=plen;
for(int i=24;i>=0;i-=1)
{
if((1<<i)&k)
{
pt=ancestor[pt][i];
}
}
return currletter[pt];
}
/*
int main()
{
int t,x;
char op,c;
cin >> t;
while(t--)
{
cin >> op;
if(op=='T')
{
cin >> c;
TypeLetter( c );
}
if(op=='U')
{
cin >> x;
UndoCommands( x );
}
if(op=='P')
{
cin >> x;
cout << GetLetter( x ) << endl;
}
}
}
*/
