题目背景

冬至奶茶快送到了，再加把劲！

题目描述

序列 $S_n$ 定义如下：

• $S_1$ 长度为 1，只包含一个元素 1；
• $S_n (n\ge 1)$ 是一个拼接序列，按照 $S_{n-1},n,S_{n-1}$ 的形式拼接而成。

例如：

• $S_2$ 是由 $S_1,2,S_1$ 拼接而成，因此 $S_2$ 为 $1,2,1$；
• $S_3$ 是由 $S_2,3,S_2$ 拼接而成，因此 $S_2$ 为 $1,2,1,3,1,2,1$。

给定 $N$，打印 $S_N$ 的完整内容。

输入格式

一个整数 $N$。

输出格式

$S_N$，每个元素用一个空格隔开。

样例1

2

1 2 1

样例2

1

1

样例3

4

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

数据范围

$1\le N \le 16$