1 2 1 3 1 2 1

题目描述

按如下方式定义序列 $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$。

输入格式

输入按以下格式从标准输入给出：

N

输出格式

用空格分隔输出 $S_N$ 的各项。

样例

2

1 2 1

如题述，$S_2$ 为 $1,2,1$。

1

1

4

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

$S_4$ 是把 $S_3$、$4$、$S_3$ 按此顺序拼接得到的序列。

数据范围

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