Description

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

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

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

Input Format

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

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

Output Format

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

5 5
1
2
3 2 4
4
3 1 5

5 4 3 2 1

Hint

【数据范围】

【本题采用捆绑测试】

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$