103444: [Atcoder]ABC344 E - Insert or Erase

Problem Statement

You are given a sequence $A=(A_1,\ldots,A_N)$ of length $N$. The elements of $A$ are distinct.

Process $Q$ queries in the order they are given. Each query is of one of the following two types:

• 1 x y : Insert $y$ immediately after the element $x$ in $A$. It is guaranteed that $x$ exists in $A$ when this query is given.
• 2 x : Remove the element $x$ from $A$. It is guaranteed that $x$ exists in $A$ when this query is given.

It is guaranteed that after processing each query, $A$ will not be empty, and its elements will be distinct.

Print $A$ after processing all the queries.

Constraints

• $1 \leq N \leq 2\times 10^5$
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $A_i \neq A_j$
• For queries of the first type, $1 \leq x,y \leq 10^9$.
• When a query of the first type is given, $x$ exists in $A$.
• For queries of the second type, $1 \leq x \leq 10^9$.
• When a query of the second type is given, $x$ exists in $A$.
• After processing each query, $A$ is not empty, and its elements are distinct.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Here, $\mathrm{Query}_i$ represents the $i$-th query and is given in one of the following formats:

$1$ $x$ $y$

$2$ $x$ 

Output

Let $A=(A_1,\ldots,A_K)$ be the sequence after processing all the queries. Print $A_1,\ldots,A_K$ in this order, separated by spaces.

Sample Input 1

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

Sample Output 1

4 5 1 3

The queries are processed as follows:

• Initially, $A=(2,1,4,3)$.
• The first query removes $1$, making $A=(2,4,3)$.
• The second query inserts $5$ immediately after $4$, making $A=(2,4,5,3)$.
• The third query removes $2$, making $A=(4,5,3)$.
• The fourth query inserts $1$ immediately after $5$, making $A=(4,5,1,3)$.

Sample Input 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

Sample Output 2

5 1 7 2 3

问题描述

你被给定一个长度为$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$。

限制条件

• $1 \leq N \leq 2\times 10^5$
• $1 \leq Q \leq 2\times 10^5$
• $1 \leq A_i \leq 10^9$
• $A_i \neq A_j$
• 对于第一种类型的查询，$1 \leq x,y \leq 10^9$。
• 当给出第一种类型的查询时，$x$存在于$A$中。
• 对于第二种类型的查询，$1 \leq x \leq 10^9$。
• 当给出第二种类型的查询时，$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

查询的处理方式如下：

• 最初，$A=(2,1,4,3)$。
• 第一个查询删除$1$，使得$A=(2,4,3)$。
• 第二个查询在$4$之后立即插入$5$，使得$A=(2,4,5,3)$。
• 第三个查询删除$2$，使得$A=(4,5,3)$。
• 第四个查询在$5$之后立即插入$1$，使得$A=(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