Description

You are given a sequence A = (A₁, ..., A_N) of length N. The elements of A are distinct.

Chyen, a baganono want to process Q queries in the order they are given. Each query is of one of the following two types:

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

Chyen wonder what the sequence A look like after Q queries. Please help him print out A after processing all the queries.

Note:

After processing each query, A will not be empty.
After processing each query, the elements of A will be distinct.

Input

The first line contains one positive integer N.

Second line contains N positive integers, A1, ..., AN

Third line contains one positive integer Q.

In the following Q lines, each line contains one query described above.

Restrictions

• 1 ≤ N ≤ 200000
• 1 ≤ Q ≤ 200000
• 1 ≤ A_i ≤ N, for all i from 1 ~ N

Subtask

for the first 5 test cases 1 ≤ N, Q ≤ 1000

Output

Let A = (A₁, ..., A_k) be the sequence after processing all the queries. Print A₁, ..., A_K in this order, separated by spaces.

Remember there is no space(' ') after A_K

Sample Input  Download

Sample Output  Download

Tags

Discuss