EDIT3 - Editor II

Background

After trying to solve problem EDIT1(Editor) and being ****ed by Brainf**k, Blue Mary decided to set another difficult problem about editor.

Description

Some definitions:

  • Text: It's a sequence that consists characters whose ASCII code is in [32,126].
  • Cursor: It's a sign for pointing out the current position. It can be at the start or the end of the text or between two consecutive characters of the text.

Editor is a structure. It contains one text and one cursor. The operations are listed below:

--------------------------------------------------------------------------
| Name        | Input format |              function                     |
--------------------------------------------------------------------------
| Move(k)     | Move k       | Move the cursor after the kth character   |
|             |              | in the text. If k=0, you should put       |
|             |              | the cursor at the start of the text.      |
--------------------------------------------------------------------------
| Insert(n,s) | Insert n s   | Insert string s whose length is n(>=1)    |
|             |              | after the cursor. The cursor doesn't move.|
--------------------------------------------------------------------------
| Delete(n)   | Delete n     | Delete n(>=1) characters after the cursor.|
|             |              | The cursor doesn't move.                  |
--------------------------------------------------------------------------
| Get(n)      | Get n        | Output n(>=1) characters after the cursor.|
--------------------------------------------------------------------------
| Prev()      | Prev         |  Move the cursor one character backward.  |
--------------------------------------------------------------------------
| Next()      | Next         |  Move the cursor one character forward.   |
--------------------------------------------------------------------------

If the text of a editor is empty, we say the editor is empty.

Here is an example._ denotes to the cursor,$ denotes to the start and the end. At start the editor is empty.

------------------------------------------------------------------------------
|         Operation          |  Text after the operation |        Output     |
------------------------------------------------------------------------------
| INSERT(13,"Balanced tree") |  $_Balanced tree$         | $$                |
------------------------------------------------------------------------------
| MOVE(2)                    |  $Ba_lanced tree$         | $$                |
------------------------------------------------------------------------------
| DELETE(5)                  |  $Ba_d tree$              | $$                |
------------------------------------------------------------------------------
| NEXT()                     |  $Bad_ tree$              | $$                |
------------------------------------------------------------------------------
| INSERT(7," editor")        |  $Bad_ editor tree$       | $$                |
------------------------------------------------------------------------------
| MOVE(0)                    |  $_Bad editor tree$       | $$                |
------------------------------------------------------------------------------
| GET(15)                    |  $_Bad editor tree$       | $Bad editor tree$ |
------------------------------------------------------------------------------

Your task is:

  • Build an empty editor.
  • Read some operations from the standard input and operate them.
  • For each Get operation, write the answer to the output.

Input

the very first line contains the number of testcases T(T<=4).T tests follow.

For each test, the first line is the number of operations N.N operations follow.

Blue Mary is so depressed with the problem EDIT1 that she decides to make the problem more difficult. So she inserts many extra line breaks in the string of the Insert operation. You must ignore them.

Except line breaks, all the characters' ASCII code are in [32,126]. There's no extra space at the end of a line.

You can assume that for each test case:

  • No invalid operation is in the input.
  • Number of move operations is no more than 50000.
  • Number of the total of insert and delete operations is no more than 4000.
  • Number of the total of prev and next operations is no more than 200000.
  • The characters inserted will not more than 2MB.The valid output will not more than 3MB.

Output

The output should contain T blocks corresponding to each testcase.

For each test case, the output should contain as many lines as the get operations in the input. Each line should contains the output of each get operation.

Example

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

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

Warning: large Input/Output data, be careful with certain languages


Added by:Fudan University Problem Setters
Date:2007-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL GOSU JS-RHINO
Resource:Chinese National Olympiad in Informatics 2003,Day 1

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.