题目描述

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

样例

2

1 2 1

1

1

4

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

样例解释

【样例1说明】 如问题陈述中所述，$S_2$ 是 1,2,1。
【样例2说明】
$S_4$ 是 $S_3$、4、$S_3$ 的连接。

来源

• AtCoder ABC247C