鸟类是神奇的动物。许多鸟类在生命中会进行各种仪式；从孔雀的求偶舞到红顶娇鹟的太空步。在本项目中，我们研究的是“排列舞”。这种仪式由一群排成一排停在电线或树枝上的鸟儿表演，如下图所示。

该仪式可以简化为基于以下几种动作序列的表演：

• 插入 (insertion)：一只新鸟加入群体，并插入到鸟群中的某个位置。
• 离开 (departure)：排中的一只鸟离开群体去休息并飞走。
• 重定位 (relocation)：排中的一只鸟从当前位置飞走，并落在（插入到）排中的其他位置。

给定鸟儿在排中的初始位置和动作序列，你的任务是计算仪式中鸟儿的最终位置。

输入格式

输入的第一行包含两个空格分隔的整数 $n$ ($1 \leqslant n \leqslant 1000$) 和 $s$ ($1 \leqslant s \leqslant 5000$)。 第二行包含 $n$ 个空格分隔的鸟名，表示仪式的初始配置（从左到右排列）。每个鸟名是一个非空字符串，最多包含 10 个（小写）字母数字字符（a 到 z，以及 0 到 9）。

接下来的 $s$ 行提供了动作序列，每行一个动作。每行根据动作类型采用以下格式之一。动作中的 bird-name 参数与输入第二行的格式相同。

• 插入：insert bird-name position position 参数是一个整数，表示插入位置左侧的鸟的数量。该参数的范围是 $[0, M]$，其中 $M$ 是插入前排中鸟的总数。位置 0 将鸟放在排的开头（最左侧），位置 $M$ 将鸟放在排的末尾（最右侧）。

• 离开：depart bird-name

• 重定位：relocate bird-name displacement displacement 参数是一个整数，可以是正数、负数或零。如果 displacement 为 0，鸟儿飞回原位。否则，如果 displacement 为正（负），鸟儿会飞过其右侧（左侧）的 $k$ 只鸟，其中 $k$ 是 displacement 的绝对值。该参数的范围是 $[-L, +R]$，其中 $L$ 和 $R$ 分别是重定位前移动的鸟在排中左侧和右侧的鸟的数量。displacement 为 $-L$ 时将鸟放在排的开头（最左侧），displacement 为 $+R$ 时将鸟放在排的末尾（最右侧）。

没有两只参与的鸟名字相同。此外，保证所有动作在执行时都是有意义的，并且在整个仪式过程中，树枝上始终至少有一只鸟。

输出格式

输出一行，包含仪式的最终配置。该行应包含排中鸟名的空格分隔列表（从左到右）。

样例

样例 1

3 1
juju ashi mashi
insert fifi 1

juju fifi ashi mashi

样例 2

3 15
m1 m2 f
insert m3 0
relocate m2 -2
relocate m1 -2
relocate m3 -2
relocate m2 -2
relocate m1 -2
relocate m3 -2
depart m2
relocate m1 1
relocate f 0
relocate m3 0
relocate f -1
relocate m3 -1
relocate m1 -2
relocate f -1

m1 f m3

样例 3

4 5
hedwig hermes fawkes errol
insert pigwidgeon 1
relocate hermes 2
depart fawkes
insert buckbeak 0
depart hedwig

buckbeak pigwidgeon errol hermes