Description

Xiao Z has a sequence of length $n$ with indices starting from $1$. Initially, the number at position $i$ is $i$. There are $m$ operations, and each operation is one of the following four types.

• 1 Sort the sequence in increasing order.
• 2 Sort the sequence in increasing order and then reverse it (i.e., sort in decreasing order).
• 3 x y Swap the numbers at indices $x$ and $y$. It is guaranteed that $x\ne y$ and $1\le x,y\le n$.
• 4 Reverse the sequence.

You need to output the sequence after $m$ operations.

Input Format

The first line contains two integers $n,m$, representing the length of the sequence and the number of operations.

The next $m$ lines each contain one operation. It is guaranteed that all operations are valid.

Output Format

Output one line containing $n$ integers, representing the sequence after all operations.

5 5
1
2
3 2 4
4
3 1 5

5 4 3 2 1

Hint

Constraints

This problem uses bundled testdata.

subtask 1 (24 pts): $1\le n,m\le 2\times 10^3$.

subtask 2 (13 pts): There is no operation of type 3.

subtask 3 (63 pts): $1\le n,m\le 10^6$.

Sample Explanation

The operations applied to the sequence are:

$1, 2, 3, 4, 5$
$1, 2, 3, 4, 5$
$5, 4, 3, 2, 1$
$5, 2, 3, 4, 1$
$1, 4, 3, 2, 5$
$5, 4, 3, 2, 1$

Translated by ChatGPT 5