//#include "crocodile.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#define shit short int
#define ll long long
#define For(i, n) for(ll i = 0; i < (ll)n; i++)
#define ffor(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rfor(i, n) for(ll i = (ll)n; i >= (ll)0; i--)
#define rffor(i, a, n) for(ll i = (ll)n; i >= (ll)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<ll, ll>
#define NEK 1000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize
#define prv1 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define sig 0.0000001
using namespace std;
vec<int> pra;
int poc = 0;
vec<char> p;
vec<int> dist;
vec<vec<int>> skok;
int jump(int x, int k) {
For(i, 32) {
if ((1 << i) & k) {
x = skok[x][i];
}
}
return x;
}
void update(int x) {
ffor(i, 1, 32) {
skok[x][i] = skok[skok[x][i - 1]][i - 1];
}
return;
}
void TypeLetter(char L) {
p.push_back(L);
skok.push_back(pra);
if (skok.size() == 1) {
skok.back()[0] = 0;
dist.push_back(0);
}
else {
skok.back()[0] = skok.size() - 2;
dist.push_back(dist.back() + 1);
}
update(skok.size() - 1);
return;
}
void UndoCommands(int U) {
int n = skok.size();
int d = n - U - 1;
p.push_back(p[d]);
skok.push_back(pra);
skok.back()[0] = skok[d][0];
update(skok.size() - 1);
dist.push_back(dist[d]);
return;
}
char GetLetter(int P) {
int k = dist.back() - P;
int x = jump(skok.size() - 1, k);
return p[x];
}
void Init() {
pra.resize(32, 0);
return;
}
/*
signed main() {
int n; cin >> n;
Init();
For(i, n) {
char x; cin >> x;
if (x == 'T') {
char a; cin >> a;
TypeLetter(a);
}
if (x == 'P') {
int a; cin >> a;
cout << GetLetter(a);
}
if (x == 'U') {
int a; cin >> a;
UndoCommands(a);
}
}
cout << '\n';
return 0;
}*/
