排队买饭

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

理工大的食堂到了饭点人可以说是相当多了,按理来说排队的时候先来的同学应该会先走,但实际情况可能并不一样,我们注意到对于一个队列往往由以下两种操作组成

当输入 1 时:代表队列最左面的同学完成了买饭操作,由于他会帮他的好朋友一起买,所以买完饭后会叫上所有与他编号相同的好朋友一起走,如果输入1时队伍已经为空则不删除。换句话说,如果序列不为空则会在序列中删除最左边的一个元素和与之编号相同的所有元素,否则不删除。

当输入 2 时:代表编号为 b 的同学想要插队买饭,由于他与编号为 a 的同学是好朋友,他会插入到队列从左往右的第一个编号为 a 的同学右边,如果队伍中没有编号为 a 的同学,他就会伤心的离开。换句话说,会在队列的从左往右的第一个 a 后面插入一个 b,如果队列中没有 a 则不插入。

需要注意的是,每次操作后都需要你判断一下队列是否为空,如果为空则输出“EMPTY”。

最后一行输出所有操作后的序列。

Input

第一行一个数 n 代表初始时序列中的元素 ( n<=1e5)

第二行 n个 int 范围内的数,最多有1000个不同的。

第三行一个数 m 代表操作的次数。(m<=1e5)

后面m行每行第一个数代表操作种类。

如果操作为 2 则再输入两个数 a,b。

Output

对于每次操作,如果操作后队列为空,则输出"EMPTY"。

所有操作完成后输出最终的序列。

(最下方提示有补充测试样例)

Sample Input

6
1 1 4 3 1 2
3
2 4 5
1
1

Sample Output

5 3 2

Hint

补充样例:

input:

6
1 1 4 3 1 2
5
2 6 5
1
1
1
1

output:

EMPTY

Source

行走的二叉树