Statement

Given an array of $n$ elements and $m$ operations, where each operation is one of the following, find the final array (1-based array);

1. Operation 1: Insert a number $y$ after the $x$th number;
2. Operation 2: Remove the $x$th element.

Input

The first line contains two integers $n,m$, where $n~(1<n\leq 10^5)$ indicates that the array contains $n$ numbers, and $m~(1\leq m\leq 10^5)$ indicates the number of operations;

The next line contains $n$ numbers $a_i$ separated by spaces, where $1 < a_i \leq 10^9$, representing the numbers stored in the array,

The following $m$ lines contain $3$ or $2$ numbers separated by spaces, where the first number represents the operation sequence number:

• If this number is $1$, then it is followed by two numbers $x$ and $y$, indicating that a number $y$ is inserted after the $x$th number;
• If this number is $2$, then it is followed by a number $x$, indicating the deletion of the $x$th number.

Output

Output the numbers in the array in order.

Samples

4 2
59 87 63 60
1 2 90
2 1

87 90 63 60