题目描述

有一根珠链和一大堆珠子，每次你可以：

• i l x 从左侧串入一个类型为 $x$ 的珠子
• o l 取出左侧最靠外的珠子
• i r x 从右侧串入一个类型为 $x$ 的珠子
• o r 取出右侧最靠外的珠子

给你若干条指令，请计算出在上述操作完成后，珠子链上珠子的类型，按从左到右的顺序输出。

输入格式

第一行是一个整数 $N$ 表示指令的总数。

接下来 $N$ 行，每行一条指令，具体格式请见题目描述部分。

输出格式

按从左到右的顺序输出珠子链上珠子的类型，每颗珠子占一行。

样例

10
i l 1
i l 1
i l 2
o r
i r 5
i l 2100
o l
o l
i r 10
o l

5
10

数据范围

对全部数据，$1≤N,M≤2×10^5,1≤x≤10^9$。