#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, 0
#define X first
#define Y second
//#define endl '\n'
constexpr ll pw(ll a, ll b, ll mod) {
return (!b ? 1 :
b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
pw(a * a % mod, b / 2, mod));
}
constexpr int N = 1e6 + 10;
constexpr int LOG = 21;
int cur, par[N], prv[N], sz[N], lg[N][LOG];
char C[N];
string ans;
void Init() {
}
void TypeLetter(char L) {
cur++;
C[cur] = L;
par[cur] = cur - 1;
prv[cur] = cur;
sz[cur] = sz[par[cur]] + 1;
lg[cur][0] = prv[par[cur]];
for (int i = 1; i < LOG; i++)
lg[cur][i] = lg[lg[cur][i - 1]][i - 1];
}
void UndoCommands(int U) {
cur++;
C[cur] = 'U';
par[cur] = cur - U - 1;
prv[cur] = prv[par[cur]];
sz[cur] = sz[par[cur]];
}
char GetLetter(int P) {
int tmp = prv[cur], cnt = sz[tmp] - P - 1;
for (int i = LOG; i--; )
if (cnt & (1 << i))
tmp = lg[tmp][i];
return C[tmp];
}
