Text Editor

This is a run-twice problem: your solution is executed twice on each test. See the rest of the statement and the input format section for more details.

Your task is to implement a simple text editor that works with strings of characters with values in range $33$ to $126$ and implements the interface described below. The length of the string is guaranteed to be at most $2^{63} - 1$ at all times. All parameters of the commands are $0$-indexed and all intervals are semi-open: $\ell$ is included while $r$ is excluded. All intervals are nonempty, and all positions and intervals are within bounds. The clipboard is initially empty.

• insert $p$ $\mathit{str}$: inserts string $\mathit{str}$ at the $p$-th position of the file. The total length of all $\mathit{str}$ is at most $10^6$.
• erase $\ell$ $r$: erases the contents of the file from the $\ell$-th to the $r$-th character.
• print $\ell$ $r$: prints the contents of the file from the $\ell$-th to the $r$-th character. The total length of the output for all print commands does not exceed $10^6$.
• copy $\ell$ $r$: copies the contents of the file from the $\ell$-th to the $r$-th character to the clipboard.
• cut $\ell$ $r$: cuts the contents of the file from the $\ell$-th to the $r$-th character to the clipboard.
• paste $p$: inserts the contents of the clipboard at the $p$-th position of the file. An empty clipboard is never pasted.
• serialize: writes the contents of the file (but not the clipboard) to the output. The output must not exceed $10^7$ characters and may use only characters in the range $33$ to $126$. The output string does not have to represent the contents of the file exactly, but your program must be able to recreate the file in response to deserialize. You must print at least one character. This command is issued only once, as the last command of the first run.
• deserialize $\mathit{str}$: $\mathit{str}$ is exactly the string printed in response to serialize. This command is issued only once, as the first command of the second run.
• undo: rolls back the changes made by the last command that changed the contents of the file (insert, erase, cut, paste, or deserialize), leaving the clipboard unchanged. If there is no previous version, the command does nothing.
• redo: redoes the last undo that is not yet undone. If there is no next version, the command does nothing. As in most text editors, any command that changes the file also erases all next versions. Other commands, such as copy, do not.

The first line contains a single integer $n$ ($1 \leq n \leq 10^4$), the number of commands. The next $n$ lines contain the commands in the format described above. The input format is the same for both runs.

Print the answers to all print and serialize commands, each on a separate line.