Text Editor

Interview

Time limit0.3sMemory limit512 MB

Summary

Simulate a line editor with cursor movement, character deletion, and insertion commands, printing the final string.

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

Problem

Implement a simple editor for a single-line string. The editor stores only lowercase English letters, and the string can grow to at most 600,000 characters.

The editor has a cursor. The cursor can be at the beginning of the string, at the end of the string, or between two adjacent characters. If the current string has length L, there are L+1 possible cursor positions.

The editor supports the following four commands.

Command	Action
L	Move the cursor one position to the left. If the cursor is already at the beginning, nothing happens.
D	Move the cursor one position to the right. If the cursor is already at the end, nothing happens.
B	Delete the character immediately to the left of the cursor. If the cursor is at the beginning, nothing happens.
P x	Insert the character `x` immediately to the left of the cursor.

You are given the initial string and then the commands in order. Print the string left in the editor after all commands are executed. The cursor starts at the end of the initial string.

Input

The first line contains the initial string. It consists only of lowercase English letters and has length at most 100,000.

The second line contains the number of commands M. M is between 1 and 500,000, inclusive.

Each of the next M lines contains one command. Every command has one of the four forms described in the problem statement.

Output

Print one line: the string in the editor after all commands have been executed.

Examples3

Example 1
Input
```
abcd
3
P x
L
P y
```
Expected output
```
abcdyx
```
Example 2
Input
```
abc
9
L
L
L
L
L
P x
L
B
P y
```
Expected output
```
yxabc
```

Example 3

Input

dmih
11
B
B
P x
L
B
B
B
P y
D
D
P z

Expected output

yxz