题目描述

我们定义序列 $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$。字之间用空格分隔。

样例 #1

样例输入 #1

2

样例输出 #1

1 2 1

样例 #2

样例输入 #2

1

样例输出 #2

1

样例 #3

样例输入 #3

4

样例输出 #3

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

提示

样例说明 1

如问题陈述中所述，$S_2$ 是 1 2 1。

样例说明 3

$S_4$ 是 $S_3,4,S_3$ 。

数据说明

• $N$ 的整数
• $1\ \leq\ N\ \leq\ 16$