#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int MAX = 1e6 + 5;
int moves = 1;
vi cuts; // position to start adding letters
vi rt(MAX); // prev time if reverting
vector<pair<int, char>> ch(MAX); // (pos, character added) at time
vi len(MAX); // length at time
string curr;
void Init() {
for (int i = 0; i < MAX; i++) {
rt[i] = i;
}
ch[0] = {-1, '!'};
}
void print() {
cout<<"cuts: ";
for (int x : cuts)
cout<<x<<" ";
cout<<endl;
cout<<"curr: "<<curr<<endl;
}
void TypeLetter(char L) {
ch[moves] = {len[moves - 1], L};
len[moves] = len[moves - 1] + 1;
moves++;
}
void UndoCommands(int U) {
rt[moves] = moves - U - 1;
len[moves] = len[moves - U - 1];
moves++;
}
string ans;
void precomp() { // find the whole string
/* cout<<"rt: ";
for (int i = 0; i < 15; i++) {
cout<<rt[i]<<" ";
}
cout<<endl;
cout<<"ch: ";
for (int i = 0; i < 15; i++) {
cout<<i<<": {"<<ch[i].fi<<", "<<ch[i].se<<"}; ";
}
cout<<endl;*/
int curr = moves - 1;
while (curr > 0) {
while (rt[curr] < curr)
curr = rt[curr];
// cout<<"at "<<curr<<endl;
ans += ch[curr].se;
curr--;
}
reverse(ans.begin(), ans.end());
// cout<<"ans: "<<ans<<endl;
}
int ctr = 0;
char GetLetter(int P) {
if (ctr == 0)
precomp();
ctr++;
return ans[P];
}
