题目描述

请实现一个被称为 Gap buffer 的文本编辑器。开始时，编辑器的文本是空的，为了定位操作的位置，编辑器还提供了一个光标。光标是指向文本的字符间隙的一个标记。

给定 n 条修改操作，请模拟编辑器在这些操作下的行为，最后输出编辑器所记录的文本内容：

插入操作：该操作还需要提供一个字符 ch 作为参数，编辑器在光标的左侧插入该字符；

前进操作：编辑器将光标向右移动一格，如果光标已经在最右端，则忽略这步操作；

后退操作：编辑器将光标向左移动一格，如果光标已经在最左端，则忽略这步操作；

删除操作：文本编辑器将删去光标右侧的字符，若光标右侧没有字符，则忽略这步操作。

输入格式

第一行：单个整数 n；
第二行到第 n+1 行：每行表示一个操作：

插入操作以字母 i 开头，后接一个字母，保证该字母是一个大写的英文字母；

删除操作仅有一个字母 d；

前进操作仅有一个字母 f；

后退操作仅有一个字母 b。

输出格式

单个字符串：表示编辑器最后所记录的文本内容。

数据范围

对于 30% 的数据，1≤n≤500；

对于 60% 的数据，1≤n≤50000；

对于 100% 的数据，1≤n≤500000。

样例数据

输入:

5

i H

i E

i L

i L

i O

输出:

HELLO

输入:

6

f

b

i A

b

i B

d

输出:

B

说明:

第一步的f和第二步的b都没有作用，接下来，每步结束后文本和光标的效果为：

A|

|A

B|A

B|