题目描述

列 $S_n$ を次のように定義します。

• $S_1$ は $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$ をすべて出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$

输出格式

$S_N$ を空白区切りで出力せよ。

题目大意

我们按如下方式定义序列 $S_n$：

$S_1$ 只包含一个整数 $1$。

$S_n$ 为 $S_{n - 1}, n, S_{n - 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

提示

制約

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

Sample Explanation 1

問題文の説明にある通り、$S_2$ は $1,2,1$ となります。

Sample Explanation 3

$S_4$ は $S_3,4,S_3$ をこの順につなげた列です。