A long time ago, programmers using DOS 3.x began to grow tired of EDLIN. Consequently, people started switching to text editors they wrote themselves...
Years later, by chance, Xiao Ming found one of those editing programs from that era. After performing some simple tests, Xiao Ming was amazed to discover that the software could perform tens of thousands of editing operations per second (of course, you cannot perform such tests manually)! Thus, Xiao Ming became obsessed with creating something similar. Can you help him?
To clarify the task, Xiao Ming provided an abstract definition of a "text editor":
Text: A sequence consisting of 0 or more characters. The ASCII codes of these characters are in the closed interval $[32, 126]$, meaning these characters are all printable characters or spaces.
Cursor: A marker used to indicate a position in a piece of text. It can be located before the first character of the text, after the last character of the text, or between any two adjacent characters of the text.
Text Editor: A program that can perform the following six operations on a piece of text and a cursor within that text. If the text is empty, we say the text editor is empty.
| Operation Name | Format in Input File | Function |
|---|---|---|
MOVE(k) |
Move k |
Move the cursor after the $k$-th character. If $k=0$, move the cursor before the first character of the text. |
INSERT(n, s) |
Insert n s |
Insert a string $s$ of length $n$ after the cursor. The cursor position remains unchanged, $n \ge 1$. |
DELETE(n) |
Delete n |
Delete the $n$ characters after the cursor. The cursor position remains unchanged, $n \ge 1$. |
GET(n) |
Get n |
Output the $n$ characters after the cursor. The cursor position remains unchanged, $n \ge 1$. |
PREV() |
Prev |
Move the cursor one character backward. |
NEXT() |
Next |
Move the cursor one character forward. |
For example, starting from an empty text editor, executing the operations INSERT(13, "Balanced tree"), MOVE(2), DELETE(5), NEXT(), INSERT(7, " editor"), MOVE(0), GET(15) in sequence will output "Bad editor tree", as shown in the table below:
| Operation | Text Before Operation | Result After Operation | ||
|---|---|---|---|---|
INSERT(13, "Balanced tree") |
` | ` | ` | Balanced tree` |
MOVE(2) |
` | Balanced tree` | `Ba | lanced tree` |
DELETE(5) |
`Ba | lanced tree` | `Ba | d tree` |
NEXT() |
`Ba | d tree` | `Bad | tree` |
INSERT(7, " editor") |
`Bad | tree` | `Bad | editor tree` |
Input Format
The first line contains an integer $T$, the number of operations.
The following lines contain $T$ operations. The format for each operation is as specified in the table above. Note that for the Insert operation, the string $s$ is provided on the line immediately following the Insert n command.
Constraints
- $T \le 2 \times 10^6$
- The total length of all inserted strings will not exceed $2 \times 10^6$.
- The characters in the strings are printable ASCII characters (ASCII 32–126).
- All operations are valid (e.g., you will not delete or get characters beyond the text boundaries, and you will not move the cursor to an invalid position).
Examples
Input 1
10 Insert 15 abcde^_^fghijkm Move 5 Next Next Insert 4 .\/. Get 4 Prev Insert 1 ^ Move 0 Get 22
Output 1
.\/. abcde^_^f.\/.ghijklmno
Note
The example input provided in the original document was slightly truncated in the description; the input above reflects the full sequence required to produce the output abcde^_^f.\/.ghijklmno.