Score: $475$ points

问题描述

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

以上为通义千问 qwen-max 翻译，仅供参考。

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