这是一个“运行两次”的问题：你的程序在每个测试点上会被执行两次。请参阅下文及输入格式部分以获取更多详细信息。

你需要实现一个简单的文本编辑器，处理字符值在 $33-126$ 范围内的字符串，并实现下述接口。字符串长度在任何时候都保证不超过 $2^{63} - 1$。所有命令的参数均为 $0$ 索引，所有区间均为半开区间（即命令接受 $\ell$ 和 $r$ 时，包含 $\ell$ 但不包含 $r$），且保证非空。所有位置和区间均在合法范围内。剪贴板初始为空。

• insert p str：该命令将字符串 str 插入到文件的第 $p$ 个位置。保证所有 str 的总长度不超过 $10^6$。
• erase l r：该命令擦除文件中从第 $\ell$ 个到第 $r$ 个字符的内容。
• print l r：执行此命令后，你应该打印文件中从第 $\ell$ 个到第 $r$ 个字符的内容。保证所有 print 命令的输出总长度不超过 $10^6$。
• copy l r：该命令将文件中从第 $\ell$ 个到第 $r$ 个字符的内容复制到剪贴板。
• cut l r：该命令将文件中从第 $\ell$ 个到第 $r$ 个字符的内容剪切到剪贴板。
• paste p：该命令将剪贴板的内容插入到文件的第 $p$ 个位置。保证不会粘贴空的剪贴板。
• serialize：执行此命令后，你应该将文件的内容（不包括剪贴板）写入输出，长度不超过 $10^7$ 个字符，且仅使用 $33-126$ 范围内的字符。输出字符串不必完全代表文件的内容，但你的程序必须能够根据 deserialize 命令恢复它。你还需要至少打印一个字符。此命令仅在第一次运行的最后执行一次。
• deserialize str：此处 str 保证是响应 serialize 命令时打印的精确字符串。此命令仅在第二次运行的开始执行一次。
• undo：执行此命令后，你应该回滚上一个改变文件内容的命令（即 insert、erase、cut、paste 或 deserialize）所做的更改，同时保持剪贴板状态不变。如果没有之前的版本，该命令不执行任何操作。
• redo：撤销上一次尚未被撤销的 undo 操作。如果没有下一个版本，该命令不执行任何操作。注意，与大多数文本编辑器一样，改变文件状态的命令也会“擦除”所有后续版本，但其他命令（例如 copy）则不会。

输入格式

两次运行的输入格式相同。

第一行包含唯一的整数 $n$ ($1 \le n \le 10^4$)，表示对文本编辑器的命令数量。

接下来的 $n$ 行包含上述格式的命令。

输出格式

在单独的行上打印所有 print 和 serialize 命令的答案。

样例

样例输入 1

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

样例输出 1

abcdef
abcdf
aabcbcdf
aabcdf
aabcbcdf
aabcbcbcdf
aabcbcbcdf
serialize:aabcbcbcdf

样例输入 2

2
deserialize serialize:aabcbcbcdf
print 0 10

样例输出 2

aabcbcbcdf