Tribute (Editor)

Interview

Time limit1sMemory limit128 MB

Summary

Simulate a buggy modal editor: given keystrokes, apply insert, delete, duplicate, reverse, and cursor commands, then print the buffer with a caret marking the cursor position.

Level: Medium4 of 10
Topics: Simulation, Implementation, String, Array
Solved: No attempts yet

Problem

This problem is not about the greatest editor in the world; it is just a tribute.

The Tenacious eDitor (td) is an attempt to clone the power of a certain modal editor. Unfortunately it is notoriously bug-ridden, and you have been asked to help fix some of those bugs.

The main problem with the current release of td is that it cannot tell apart text that is meant to appear on a line from commands. Whenever a user wants to type an x, the editor instead interprets it as a command to delete the previous character. Thankfully commands are case-sensitive and each command is a single letter, so any line of text can still be produced — as long as you are willing to write it in a way that looks like it was typed by a wannabe teenage hacker.

Editing happens in an edit buffer, which starts out empty. The cursor rests in a gap, one of the positions surrounding each printed character. When a non-command character is entered, it is inserted immediately to the right of the cursor and the cursor moves to the gap to the right of the new character. A line with no characters has a single gap; a line with one printable character has two gaps (one before and one after); a line with two printable characters has three gaps; and so on.

The currently implemented commands are:

Command key	Result	Cursor location after the operation
`x`	Delete the character immediately to the left of the cursor.	One gap to the left.
`K`	Delete every non-space character to the left of the cursor, stopping at the first space or the beginning of the line; if the character to the left is a space, delete nothing.	The gap to the right of the character it stopped at.
`c`	Duplicate the character to the left of the cursor, inserting the copy to the right of the cursor.	The gap to the right of the duplicated character.
`D`	Duplicate every non-space character to the left of the cursor, stopping at the first space or the beginning of the line, inserting the copies to the right of the cursor; if the character to the left is a space, duplicate nothing.	The gap to the right of the rightmost duplicated character.
`R`	Reverse every non-space character to the left of the cursor, stopping at the first space or the beginning of the line; if the character to the left is a space, reverse nothing.	No change.
`p`	Delete every character to the left of the cursor.	Leftmost gap.
`W`	Delete every character to the right of the cursor.	No change.
`h`	Move the cursor one gap to the left.	One gap to the left.
`L`	Move the cursor one gap to the right.	One gap to the right.
`f`	Move the cursor to the first gap on the line.	Leftmost gap.
`G`	Move the cursor to the last gap on the line.	Rightmost gap.
any other character	Insert the character into the edit buffer to the right of the cursor.	One gap to the right.

For this problem the only possible characters are uppercase letters, lowercase letters, digits, and spaces.

When a character is inserted in the middle of a line, every character after it shifts one position to the right (insert mode); when a character is deleted anywhere other than the end of a line, every character after it shifts one position to the left.

Any command that cannot do anything meaningful — moving past the first or last gap, deleting when there is nothing to delete, and so on — does nothing at all, and never appears as a printed character.

Each input line is an independent td session; every session starts with an empty edit buffer.

Given the keystrokes typed by a user, determine the text that actually ends up in the buffer.

Input

The first line contains a single integer $N$ ( $1 \le N \le 100$ ), the number of data sets.

Each data set is a single line of characters as described above, with no leading or trailing whitespace. Each line has at least $1$ and at most $100$ characters and represents the keystrokes a user entered during one td session.

Output

For each data set, print the final contents of the edit buffer, with a caret (^) marking the position of the cursor.

Examples1

Example 1

Input

2
Deletex bigdeleteKduPc bigduPD esreverR midinhhdleGxx midelletehhhxGfmoo
THis ratHer obnoXious line oF CHaraCters surPrisingly triggers no Commands

Expected output

moo^elet duPP bigduPbigduP reverse middle midelete
THis ratHer obnoXious line oF CHaraCters surPrisingly triggers no Commands^