E - Insert or Erase Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。A の要素は相異なります。

Q 個のクエリが与えられるので順に処理してください。各クエリは次の 2 種類のどちらかです。

  • 1 x y ： A 内の要素 x の直後に y を挿入する。このクエリが与えられる時点で、A には x が存在することが保証される。
  • 2 x ： A 内の要素 x を削除する。このクエリが与えられる時点で、A には x が存在することが保証される。

各クエリの処理後、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 種類目のクエリにおいて、1 \leq x,y \leq 10^9
  • 1 種類目のクエリが与えられる時点で、A には x が存在する
  • 2 種類目のクエリにおいて、1 \leq x \leq 10^9
  • 2 種類目のクエリが与えられる時点で、A には x が存在する
  • 各クエリの処理後、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 番目のクエリにより 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) となる。

入力例 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

Score: 475 points

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