问题描述

火焰车正在研究一个有趣的序列。我们按如下方式定义序列 $S_n$：

• $S_1$ 是一个只包含整数 $1$ 的序列。
• 对于 $n \geq 2$，$S_n$ 是由 $S_{n-1}$、 $n$、 $S_{n-1}$ 顺次连接而成的序列。

例如：

• $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$，表示需要生成的序列编号。

输出格式

• 输出一行，表示序列 $S_N$，各元素之间用空格分隔。

2

1 2 1

1 

1  

4 

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

数据范围

$1 \le N \le 16$