题目描述

分形序列 S$_n$ 递归定义如下：

• S$_1$ 只包含一个整数 1。

• S$_n$ 为 S$_{n-1}$, n , S$_{n-1}$ 构成的序列。

给定 n，输出序列 S$_n$。

输入格式

n

输出格式

输出一行  S$_n$，用空格隔开

样例

输入样例#1

2

输出样例#1

1 2 1

输入样例#2

1

输出样例#2

1

输入样例#3

4

输出样例#3

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

数据范围与提示

• 1<=n<=16