题目描述

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

• $S_1$ 是一个长度为 1 的序列，包含一个数字 1。
• 对于 $n \geq 2$，$S_n$ 是通过将 $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$

输出格式

打印题目要求的序列。

2

1 2 1

1

1

4

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

提示

数据范围

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

样例 3 解释

该序列的前一部分是 $S_3$，中间是 $4$，后一部分是 $S_3$。