Background

Original statement:

$\color{gray}\text{zrmpaul}$ has an array consisting of $n$ integers: $a_1,a_2,...,a_n$. The initial value of $a_i$ is $i(1\le i\le n)$. There are $m$ operations, including four types as follows.

Type $1$: 1 sort the array.
Type $2$: 2 sort the array and reverse it.
Type $3$: 3 x y swap $a_x,a_y$. It is guaranteed that $x$ is not equal to $y$, and $1\leq x ,y \leq n$.
Type $4$: 4 reverse the array.

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

First line with two intergers $n,m(1\leq n,m\leq 10^6)$.

Next $m$ lines are the operations.

One line, $n$ numbers, the array.

Problem 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