Description

给定 $t,n$，以及长度为 $n$ 的排列 $a_{1\sim n}$，两个人轮流进行以下操作：

• 选择 $1\le i,j\le n$ 并且交换 $a_i,a_j$（$i, j$ 可以相同）。

两个人一共进行 $t$ 次操作（一个人算一次操作）。先手希望最终的排列字典序越小越好，后手希望字典序越大越好。若两人足够聪明，问最终得到的排列。

Input Format

第一行两个正整数 $t,n$。

第二行 $n$ 个 $1\sim n$ 的正整数，表示排列 $a$。

Output Format

一行一个排列，表示最终答案。

1 6
1 2 4 3 6 5

1 2 3 4 6 5

Hint

对于 $100\%$ 的数据，$1 \le t \le 10^{18}$，$1 \le n \le 10^5$，$a_1\sim a_n$ 组成 $1\sim n$ 的排列。