Description

我们定义序列 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。

Input Format

给定 N。

Output Format

请输出整个序列 S~N~。字之间用空格分隔。

2

1 2 1

1

1

4

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

Hint

数据范围与提示

【样例1说明】 如问题陈述中所述， S~2~是 1,2,1。 【样例2说明】 S~4~是 S~3~、4、S~3~ 的连接。

【数据范围】 N是一个整数 1≤N≤16