Cut and Paste P60837

Statement

We need to implement an editor consisting of a buffer of length $n\ge 0$ and a cursor placed on some character $0 \le i < n$ of the buffer (or at the end of the buffer if $i=n$ ). The editor must support some basic operations (moving the cursor, inserting or removing characters) and two special commands: Cut (text is removed from the buffer and moved to the clipboard) and Paste (text is removed from the clipboard and moved to the buffer). Removing pasted text from the clipboard prevents the buffer from growing exponentially in the number of commands.

Implement such an editor, starting with an empty buffer ( $i = n = 0$ ).

Input

Input consists of at most $10^6$ commands, one per line, of the following form:

M $x$ : Move the cursor $x$ chars forward (or backward if $x<0$ ). Don’t go past the beginning or the end of the buffer.
I $c$ : Insert the lowercase letter $c$ at the cursor. Move the cursor one char to the right.
D: If the cursor is not at the end of the buffer, delete the char at the cursor. The cursor does not move.
C $x$ : Starting at the cursor, cut $x>0$ chars from the buffer (less, if you reach the buffer’s end) and move them to the clipboard, overwriting it. The cursor does not move.
P: Paste (insert) the chars from the clipboard at the cursor. The cursor, and the char the cursor was on, moves after the inserted text. Erase the clipboard.
O: Output the contents of the buffer. Print a ‘’ before the char where the cursor is.
R: Reset the editor: erase the buffer, the clipboard, and set the cursor position to $i = 0$ .

Output

Output one line for each O command.

Public test cases

Input

O
I a
O
I b
I c
I d
O
D
D
D
O
M -2
I z
O
D
O

Output

*
a*
abcd*
abcd*
abz*cd
abz*d

Input

I a
I b
I c
I d
M -1
D
I e
I f
I g
I h
O
M -5
C 3
O
M 100
M -1
P
O
P
O
R
O

Output

abcefgh*
ab*gh
abgcef*h
abgcef*h
*

Information

Author: Omer Gimenez
Language: English
Official solutions: C++
User solutions: C++