#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;
void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
cout << H << ' ';
debug_out(T...);
}
#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)
const int maxn = 1e6 + 10;
int seg[maxn << 2][4], lazy[maxn << 2][3];
string s;
vector<pii> val;
void shift(int v, int l, int r);
void add(int v, int l, int r, int idx){
if (idx < l || r <= idx) return;
if (l + 1 == r){
seg[v][1] = 1;
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
add(v << 1, l, mid, idx);
add(v << 1 | 1, mid, r, idx);
for (int i = 0; i < 4; i++){
seg[v][i] = seg[v << 1][i] + seg[v << 1 | 1][i];
}
}
void update(int v, int l, int r, int ql, int qr, int type){
if (qr <= l || r <= ql) return;
if (ql <= l && r <= qr){
if (type == 0){
swap(seg[v][0], seg[v][1]);
lazy[v][0] ^= 1;
}
else if (type == 1){
swap(seg[v][2], seg[v][3]);
lazy[v][1] ^= 1;
}
else{
swap(seg[v][0], seg[v][2]);
swap(seg[v][1], seg[v][3]);
swap(lazy[v][0], lazy[v][1]);
lazy[v][2] ^= 1;
}
return;
}
shift(v, l, r);
int mid = (l + r) >> 1;
update(v << 1, l, mid, ql, qr, type);
update(v << 1 | 1, mid, r, ql, qr, type);
for (int i = 0; i < 4; i++){
seg[v][i] = seg[v << 1][i] + seg[v << 1 | 1][i];
}
}
int find(int v, int l, int r, int idx){
if (seg[v][1] + seg[v][3] < idx) return -1;
if (l + 1 == r) return l;
shift(v, l, r);
int mid = (l + r) >> 1;
int tmp = find(v << 1, l, mid, idx);
if (tmp == -1){
idx -= seg[v << 1][1] + seg[v << 1][3];
tmp = find(v << 1 | 1, mid, r, idx);
}
return tmp;
}
void shift(int v, int l, int r){
int lc = v << 1;
int rc = lc | 1;
int mid = (l + r) >> 1;
for (int i = 2; ~i; i--){
if (lazy[v][i]){
update(lc, l, mid, l, mid, i);
update(rc, mid, r, mid, r, i);
lazy[v][i] = 0;
}
}
}
void Init() {}
void TypeLetter(char L){
s.push_back(L);
add(1, 0, maxn, s.size()-1);
}
void UndoCommands(int U) {
s.push_back('?');
update(1, 0, maxn, s.size()-U, s.size(), 2);
int tmp = s.size()-U;
while(!val.empty() && val.back().S >= tmp){
tmp = min(tmp, val.back().F);
val.pop_back();
}
val.push_back({tmp, s.size()});
update(1, 0, maxn, tmp, s.size(), 1);
}
char GetLetter(int P) {
return s[find(1, 0, maxn, P+1)];
}
