题目背景

原题面：

$\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.

题目描述

小 Z 有一个下标从 $1$ 开始并且长度为 $n$ 的序列，初始时下标为 $i$ 位置的数字为 $i$。有 $m$ 个操作，每个操作会是以下四种之一。

• 1 对序列从小到大进行排序。
• 2 对序列从小到大进行排序后将其翻转，(译者注：就是从大到小排序）。
• 3 x y 将下标为 $x,y$ 的数交换位置。保证 $x\neq y$ 且 $1\le x,y\le n$。
• 4 将序列翻转。

你要输出在 $m$ 次操作后的序列。

输入格式

第一行两个整数 $n,m$ ，表示序列的长度以及操作的数量。

接下来 $m$ 行，每行一个操作。保证操作合法。

输出格式

一行包含 $n$ 个整数，表示操作后的序列。

5 5
1
2
3 2 4
4
3 1 5

5 4 3 2 1

提示

【数据范围】

【本题采用捆绑测试】

subtask 1（24pts）: $1\leq n,m\leq 2 \times 10^3$ 。

subtask 2（13pts）: 没有操作三。

subtask 3（63pts）: $1\leq n,m\leq 10^6$ 。

【样例解释】

序列经过的操作为：

$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$