题目描述

我们定义序列 $S_n$ 如下。

• $S_1$ 是长度为 $1$ 的序列，只包含一个 $1$。
• $S_n$（$n$ 是大于或等于 $2$ 的整数）是通过将 $S_{n-1}$、$n$ 和 $S_{n-1}$ 依次拼接而得到的序列。

例如，$S_2$ 和 $S_3$ 定义如下。

• $S_2$ 是按顺序将 $S_1$、$2$ 和 $S_1$ 拼接而成的，因此它是 $1,2,1$。
• $S_3$ 是按顺序将 $S_2$、$3$ 和 $S_2$ 拼接而成的，因此它是 $1,2,1,3,1,2,1$。

给定 $N$，打印完整的序列 $S_N$。

约束条件

• $N$ 是一个整数。
• $1 \leq N \leq 16$

输入

输入以以下格式从标准输入获得：

$N$

输出

以空格分隔的形式打印 $S_N$。

示例输入 1

2

示例输出 1

1 2 1

根据题目描述，$S_2$ 是 $1,2,1$。

示例输入 2

1

示例输出 2

1

示例输入 3

4

示例输出 3

1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

$S_4$ 按顺序将 $S_3$、$4$ 和 $S_3$ 拼接而成。