插入或删除

题目描述

给定长度为 $N$ 的序列 $A=(A_1,\ldots,A_N)$。$A$ 的元素互不相同。

按给定顺序处理 $Q$ 个查询。每个查询为以下两种类型之一：

• 1 x y：在 $A$ 中元素 $x$ 的紧后面插入 $y$。保证给出该查询时 $x$ 存在于 $A$ 中。
• 2 x：从 $A$ 中删除元素 $x$。保证给出该查询时 $x$ 存在于 $A$ 中。

保证处理完每个查询后，$A$ 非空，且元素互不相同。

处理完所有查询后，输出 $A$。

输入格式

输入按以下格式从标准输入给出：

N
A_1 … A_N
Q
Query_1
⋮
Query_Q

这里，$\mathrm{Query}_i$ 表示第 $i$ 个查询，按以下两种格式之一给出：

1 x y

2 x

输出格式

设处理完所有查询后的序列为 $A=(A_1,\ldots,A_K)$。按顺序以空格分隔输出 $A_1,\ldots,A_K$。

样例

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

4 5 1 3

查询按如下方式处理：

• 初始时 $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)$。

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

5 1 7 2 3

数据范围

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