Simple Editor

Interview

Time limit8sMemory limit1024 MB

Summary

Apply each keystroke in order (insert a lowercase letter left of the cursor, or move the cursor left or right) and print the final string for each dataset.

Level: Easy3 of 10
Topics: Stack, Simulation, String
Solved: No attempts yet

Problem

You are a fairy who works inside a computer. Your job today is to operate an editor based on keyboard input.

You overslept! When you rush to your workplace, keyboard inputs have already piled up without being processed. What you must do now is display the string that results from processing all the pending inputs in order.

Let us review the situation. At first the editor holds no string, and there is only one vertical line (the cursor) that marks where characters are inserted.

Keyboard input comes in three kinds.

INSERT c: Insert the character c to the left of the cursor. More precisely, if no character is immediately to the left of the cursor, c goes at that position. If a character is there, c goes between that character and the cursor.
LEFT _: Move the cursor one character to the left. If no character is to the left of the cursor, do nothing. The _ is a dummy that keeps the input format uniform.
RIGHT _: Move the cursor one character to the right. If no character is to the right of the cursor, do nothing. The _ is a dummy that keeps the input format uniform.

Print the string after processing all pending inputs in order. You do not need to print the cursor.

Input

The input consists of multiple datasets. The number of datasets does not exceed 50. Each dataset has the following format.

N
a_1
⋮
a_N

The first line contains an integer $N$ , the number of keyboard inputs. It satisfies $1 \leq N \leq 1000$ .

The next $N$ lines give the keyboard inputs $a_i$ in order. Each $a_i$ has one of the following forms.

INSERT c: c is a single lowercase English letter.
LEFT _
RIGHT _

It is guaranteed that at least one INSERT c input exists.

The input ends with a line containing a single zero.

Output

For each dataset, print on one line the string obtained after processing all keyboard inputs in order.

Examples1

Example 1

Input

5
INSERT a
INSERT g
LEFT _
LEFT _
INSERT j
19
INSERT z
INSERT y
LEFT _
LEFT _
LEFT _
INSERT a
RIGHT _
RIGHT _
INSERT a
RIGHT _
INSERT n
LEFT _
LEFT _
RIGHT _
LEFT _
LEFT _
INSERT n
LEFT _
INSERT u
0

Expected output

jag
azunyan