You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

给定一个长度为 $N$ 的序列 $A$，$A$ 中的元素互不相同。

请你按照给定的顺序处理 $Q$ 次操作，每次操作有两种类型：

• 1 x y：在元素 $x$ 后面插入 $y$，保证 $x$ 在 $A$ 中。
• 2 x：把 $x$ 从 $A$ 中移除，保证 $x$ 在 $A$ 中。

处理完所有操作之后，请输出 $A$。

输入格式

输入将以以下形式从标准输入给出。

$N$ $A_1$ $\ldots$ $A_N$ $Q$ $\mathrm{Query}_1$ $\vdots$ $\mathrm{Query}_Q$

这里，$\mathrm{Query}_i$ 表示第 $i$ 个查询，并且以如下形式给出。

$1$ $x$ $y$

$2$ $x$

输出格式

将所有查询处理完毕后的数列 $A$ 记为 $(A_1,\ldots,A_K)$ 。请按此顺序以空格分隔输出 $A_1,\ldots,A_K$ 。

样例输入 #1

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

样例输出 #1

4 5 1 3

样例输入 #2

6
3 1 4 5 9 2
7
2 5
1 3 5
1 9 7
2 9
2 3
1 2 3
2 4

样例输出 #2

5 1 7 2 3

限制条件

• $1 \leq N \leq 2\times10^5$
• $1 \leq Q \leq 2\times10^5$
• $1 \leq A_i \leq 10^9$
• $A_i \neq A_j$
• 对于第1类查询，$1 \leq x, y \leq 10^9$，当给出第1类查询时，$A$ 中存在 $x$
• 对于第2类查询，$1 \leq x \leq 10^9$，当给出第2类查询时，$A$ 中存在 $x$
• 每个查询处理后，$A$ 不为空，且元素各不相同
• 输入均为整数

示例解释1

查询按如下方式处理：

• 最初 $A = (2, 1, 4, 3)$ 。
• 通过第1个查询删除1。$A$ 变为 $(2, 4, 3)$ 。
• 通过第2个查询，在4之后立即插入5。$A$ 变为 $(2, 4, 5, 3)$ 。
• 通过第3个查询删除2。$A$ 变为 $(4, 5, 3)$ 。
• 通过第4个查询，在5之后立即插入1。$A$ 变为 $(4, 5, 1, 3)$ 。