Description

冰块喜欢排队。总共有 $n$ 个冰块现在要排队，每一个冰块都是独一无二的，所以他们都有一个唯一的编号（从 $1$ 到 $n$）。现在冰块们已经排好队了（一个长度为 $n$ 的排列），Alice 和 Bob 想跟冰块们玩一个游戏。Alice 先手，Bob 后手，轮流进行操作。每次选择 $i$ 号冰块和 $j$ 号冰块进行位置交换，或者可以选择不换。这样进行 $k$ 轮之后，得到的冰块序列是一个长度为 $n$ 的排列，Alice 希望这个排列字典序最小，Bob 希望这个排列字典序最大。若两人都足够聪明，问最终的排列会是什么。

Format

Input

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

第二行 $n$ 个 $1\sim n$ 的正整数，表示初始冰块序列的编号。

Output

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

Samples

1 6
1 2 4 3 6 5

1 2 3 4 6 5

Limitation

$1\mathrm{s}, 512\mathrm{MB}$

Subtasks

对于 $100\%$ 的数据，$1\leqslant k\leqslant 10^{18},1\leqslant n\leqslant 10^{5}$，$a_i$ 组成 $1\sim n$ 的排列。