#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define rep(i, n) for(int i = 0; i < (n); i += 1)
#define len(a) ((int)(a).size())
#ifdef LOCAL
bool local = true;
#else
bool local = false;
#endif
const int max_nodes = 5e6;
mt19937_64 rnd(122343);
string container;
struct node {
int xl = 0, xr = 0;
int l = -1;
int r = -1;
ull size = 0;
};
int cur_size = 0;
node t[max_nodes];
int new_node() {
assert(cur_size < max_nodes);
t[cur_size] = node();
return cur_size++;
}
int new_node(int v) {
assert(cur_size < max_nodes and v < cur_size and v >= 0);
t[cur_size] = t[v];
return cur_size++;
}
ull size(int v) {
return v == -1 ? 0 : t[v].size;
}
void upd(int v) {
if (v == -1) return;
t[v].size = size(t[v].l) + size(t[v].r) + t[v].xr - t[v].xl + 1;
}
int merge(int u, int v) {
if (u == -1 or v == -1) return u + v + 1;
ull szu = size(u);
ull szv = size(v);
if (rnd() % (szu + szv) < szu) {
u = new_node(u);
t[u].r = merge(t[u].r, v);
upd(u);
return u;
} else {
v = new_node(v);
t[v].l = merge(u, t[v].l);
upd(v);
return v;
}
}
pair<int, int> split(int v, ull k) {
if (v == -1) return make_pair(-1, -1);
if (k == 0) return make_pair(-1, v);
if (k >= size(v)) return make_pair(v, -1);
v = new_node(v);
ull vlen = (t[v].xr - t[v].xl + 1);
ull lsize = size(t[v].l);
if (k <= lsize) {
auto [a, b] = split(t[v].l, k);
t[v].l = b;
upd(v);
return make_pair(a, v);
}
if (k >= lsize + vlen) {
auto [a, b] = split(t[v].r, k - lsize - vlen);
t[v].r = a;
upd(v);
return make_pair(v, b);
}
int u = new_node(v);
t[u].xr = t[u].xl + (k - lsize) - 1;
t[v].xl = t[u].xr + 1;
t[u].r = -1;
t[v].l = -1;
upd(u);
upd(v);
return make_pair(u, v);
}
array<int, 3> split(int v, ull l, ull r) {
auto [ab, c] = split(v, r);
auto [a, b] = split(ab, l);
return { a, b, c };
}
void print_rec(int v) {
if (v == -1) return;
assert(size(v) <= 1e6);
print_rec(t[v].l);
for (int i = t[v].xl; i <= t[v].xr; i += 1) {
cout << container[i];
}
print_rec(t[v].r);
}
void print(int v) {
print_rec(v);
cout << "\n";
}
vector<int> checkpoints;
int cur = 0;
int clipboard = -1;
string encode(string s) {
string t;
for (auto x : s) {
if (x == ' ') {
t += "\\_";
continue;
}
if (x == '\\') {
t += "\\\\";
continue;
}
t += x;
}
return t;
}
string decode(string s) {
string t;
bool special = false;
for (auto x : s) {
if (special) {
assert(x == '\\' or x == '_');
if (x == '\\') t += '\\';
else if (x == '_') t += ' ';
else assert(0);
special = false;
continue;
}
if (x == '\\') {
special = true;
continue;
}
t += x;
}
assert(!special);
return t;
}
template<class T>
void do_some_things(T& in, bool silent = false) {
int n;
in >> n;
stringstream commands;
commands << n << " ";
rep(i, n) {
string command;
in >> command;
commands << command << " ";
if (command == "deserialize") {
string serialized;
cin >> serialized;
stringstream super;
super << decode(serialized);
do_some_things(super, true);
int v = checkpoints[cur];
checkpoints = { -1, v };
cur = 1;
clipboard = -1;
} else if (command == "insert") {
ull p;
in >> p;
string s;
in >> s;
commands << p << " " << s << " ";
int xl = len(container);
container += s;
int xr = len(container) - 1;
checkpoints.resize(cur + 1);
int v = checkpoints[cur];
auto [a, c] = split(v, p);
int b = new_node();
t[b].xl = xl; t[b].xr = xr; upd(b);
v = merge(merge(a, b), c);
checkpoints.push_back(v);
cur++;
} else if (command == "erase") {
ull l, r;
in >> l >> r;
commands << l << " " << r << " ";
checkpoints.resize(cur + 1);
int v = checkpoints[cur];
auto [a, b, c] = split(v, l, r);
v = merge(a, c);
checkpoints.push_back(v);
cur++;
} else if (command == "print") {
ull l, r;
in >> l >> r;
commands << l << " " << r << " ";
int v = checkpoints[cur];
auto [a, b, c] = split(v, l, r);
if (!silent) {
print(b);
}
} else if (command == "copy") {
ull l, r;
in >> l >> r;
commands << l << " " << r << " ";
int v = checkpoints[cur];
auto [a, b, c] = split(v, l, r);
clipboard = b;
} else if (command == "cut") {
ull l, r;
in >> l >> r;
commands << l << " " << r << " ";
checkpoints.resize(cur + 1);
int v = checkpoints[cur];
auto [a, b, c] = split(v, l, r);
clipboard = b;
v = merge(a, c);
checkpoints.push_back(v);
cur++;
} else if (command == "paste") {
ull p;
in >> p;
commands << p << " ";
checkpoints.resize(cur + 1);
int v = checkpoints[cur];
auto [a, c] = split(v, p);
int b = clipboard;
v = merge(merge(a, b), c);
checkpoints.push_back(v);
cur++;
} else if (command == "undo") {
if (cur > 0) {
cur--;
}
} else if (command == "redo") {
if (cur + 1 < len(checkpoints)) {
cur++;
}
} else if (command == "serialize") {
if (!silent) {
string serialized = encode(commands.str());
cout << serialized << "\n";
}
}
}
}
int32_t main() {
if (local) {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
checkpoints = { -1 };
cur = 0;
container = "";
clipboard = -1;
do_some_things(cin);
return 0;
}
/*
17
insert 0 abcdef
print 0 6
erase 4 5
print 0 5
copy 0 3
paste 1
print 0 8
cut 2 4
print 0 6
undo
print 0 8
paste 6
print 0 10
redo
redo
print 0 10
serialize
2
deserialize 17\_insert\_0\_abcdef\_print\_0\_6\_erase\_4\_5\_print\_0\_5\_copy\_0\_3\_paste\_1\_print\_0\_8\_cut\_2\_4\_print\_0\_6\_undo\_print\_0\_8\_paste\_6\_print\_0\_10\_redo\_redo\_print\_0\_10\_serialize\_
print 0 10
*/