Background

Special for beginners, ^_^

Description

石老师为了装修迎新晚会，做了一根长度为 $n$ 的彩灯条。

王老师喜欢时不时来指导一下工作，他的指导就是指着灯条上的某一个灯珠说，他有一个xx颜色的灯珠必须放在这个灯珠的后面。

徐校长也喜欢时不时来指导一下工作，他的指导就是指着灯条上的某一个灯珠说，这个颜色的灯珠不符合睿爸信奥的办学理念，必须移除。

黄老师也来了，他同样喜欢时不时来指导一下工作，他的指导就是指着灯条上的某一个灯珠说，他有一个yy颜色的灯珠必须放在这个灯珠的前面。

上面的每一个彩灯珠可以用一个不超过1e9的整数表示其颜色。

每次操作后，灯条都至少有一颗灯珠且灯条上没有颜色相同的灯珠。

请输出最后的灯条长啥样。

Format

Input

第一行一个正整数 $N（\le5\times10^5）$ 表示初始的灯条由 $N$个彩珠组成（保证两两不同）。

接下来一行，$A_1 ... A_N$，表示灯珠的颜色。

第三行一个正整数 $Q（\le5\times10^5）$。

接下来 $Q$ 行，每行是其中的一种：

1 $x$ $y$ 表示将 $y$ 插入到 $x$ 的后面。

2 $x$ 表示删除 $x$ 。

3 $x$ $y$ 表示将 $y$ 插入到 $x$ 的前面。

Output

按照顺序输出最后灯条中每个灯珠的颜色，相邻两个数中间插入一个空格。

Samples

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

4 5 1 6 3

Limitation

1s, 1024KiB for each test case.