Text Editor

Time limit2sMemory limit256 MB

Summary

Simulate a text editor with cursor moves, inserts, deletes, and reads over a large text, where each Get returns the n characters after the cursor.

Level: Medium6 of 10
Topics: Implementation, Linked list, String
Solved: No attempts yet

Problem

Long ago, DOS 3.x programmers grew tired of EDLIN, so they gradually switched to editors they wrote themselves.

Many years later, Alex stumbled upon a text editor from that era. After some basic testing, he discovered that it can perform tens of thousands of edit operations per second (of course, you cannot run these tests by hand). Alex now spends sleepless nights trying to build a product like this himself. Can you help him?

To make the term "text editor" concrete, Alex defined the following.

text: a sequence of 0 or more ASCII characters with values in $[32, 126]$ (spaces and visible characters).
cursor: a mark within a block of text that indicates a position. It may be at the beginning of the text, at the end of the text, or between any two adjacent characters.
text editor: a program that holds a block of text and a single cursor, and can perform the six operations below. If the block of text is empty, the text editor is empty.

Operation	Input Format	Function
Move(k)	`Move k`	Moves the cursor to immediately after the $k$ -th character in the text. If $k = 0$ , the cursor moves to the start of the text.
Insert(n, s)	`Insert n↵ s`	Inserts a string $s$ of length $n$ ( $n \geq 1$ ) at the cursor. The cursor position does not change.
Delete(n)	`Delete n`	Deletes the $n$ ( $n \geq 1$ ) characters following the cursor. The cursor position does not change.
Get(n)	`Get n`	Outputs the $n$ ( $n \geq 1$ ) characters following the cursor. The cursor position does not change.
Prev	`Prev`	Moves the cursor backward by one character.
Next	`Next`	Moves the cursor forward by one character.

For example, starting from an empty editor, the operations Insert(13, "Balanced tree"), Move(2), Delete(5), Next(), Insert(7, "editor"), Move(0), and Get(16) output "Bad editor tree".

Your task is to:

Create an empty text editor.
Read operations from the input and execute them.
For each Get() operation, output the correct contents.

Constraints:

The number of Move() operations is at most 50000. The total number of Insert() and Delete() operations is at most 4000. The total number of Prev() and Next() operations is at most 200000.
Each Insert() operation inserts at most 2M characters ( $1 \mathrm{M} = 1024 \times 1024$ ). The correct output is at most 3M characters long.
Each Delete() and Get() operation always has enough characters after the cursor. Move(), Prev(), and Next() never move the cursor to an invalid position. All operations are valid.

Input

The first line contains an integer $t$ , the number of operations. The next $t$ lines contain the operations.

The string after an Insert() operation may span multiple lines. Ignore the line breaks in it. Apart from line breaks, every character in the input has an ASCII value in $[32, 126]$ . There are no trailing spaces.

Output

For each Get() operation, print the requested text on its own line.

Examples1

Example 1

Input

15
Insert 26
abcdefghijklmnop
qrstuv wxy
Move 16
Delete 11
Move 5
Insert 1
^
Next
Insert 1
_
Next
Next
Insert 4
.\/.
Get 4
Prev
Insert 1
^
Move 0
Get 22

Expected output

.\/.
abcde^_^f.\/.ghijklmno