蝴蝶变换

题目描述

相信你一定学过快速傅里叶变换(FFT)，常规的多项式乘法需要依次遍历两个多项式的每一项，分别相乘再相加，而这样的复杂度显然是 $O(n^2)$ 的，而FFT为我们提供了一种在 $O(n\log_2n)$ 复杂度内解决多项式乘法的方案：通过将多项式转化为点值表示，我们可以在 $O(n)$ 的复杂度内完成多项式乘法，而FFT则可以帮助我们在 $O(n\log_2n)$ 复杂度内快速将多项式的系数表示变为点值表示，并在相同复杂度内将点值表示还原为系数表示。而FFT的核心部分正是采用了复数单位根的性质，通过将复数单位根带入多项式的未知数，并将奇数和偶数位置的单位根抽出重新排列，通过单位根的性质快速计算出点值表达式。

ps:以上背景不影响做题。

当然，本题并不会要求你掌握FFT，你只需要实现FFT中的一个小部分功能：蝴蝶变换 即可。对于复数单位根的系数序列，我们钦定其有 $8$ 项，我们不妨记为：

$$w_0, w_1, w_2, w_3, w_4, w_5, w_6, w_7$$

蝴蝶变换会将上述序列按照顺序依次抽出其奇数位置的项，和偶数位置的项（不改变相对位置），将所有的奇数位置的项放到序列的左端，偶数位置的项放到序列右端：

$$w_0, w_2, w_4, w_6 \ | \ w_1, w_3, w_5, w_7$$

然后，若划分出的序列长度大于 $1$，则对两边的序列再次进行上述操作，直到划分出的序列长度大小为 $1$：

$$w_0, w_4 \ | \ w_2, w_6 \ | \ w_1, w_5 \ | \ w_3, w_7$$$$w_0 \ | \ w_4 \ | \ w_2 \ | \ w_6 \ | \ w_1 \ | \ w_5 \ | \ w_3 \ | \ w_7$$

我们将最终得到的序列 $0,4,2,6,1,5,3,7$ 称为 $8$ 的蝴蝶变换序列。由于Orange刚刚学习完FFT，对蝴蝶变换的内容掌握不够熟练，因此他想请你帮助他求出 $n$ 的蝴蝶变换序列。Orange保证 $n$ 是一个2的整数次幂。

输入格式

输入共一行，包含一个整数 $n$，表示Orange给出的整数 $n$。

数据范围

$1 \le n \le 2^{20}$

输出格式

输出一行，包含 $n$ 个整数，中间以空格分离，表示 $n$ 对应的蝴蝶变换序列。

样例 #1

样例输入 #1

8

样例输出 #1

0 4 2 6 1 5 3 7