Background

又是一个星夜，QuQ望着繁星点点的夜空，正发着呆

Description

他突发奇想，他把星空分成几个区块并给每个区块标号。
他惊喜地发现如果按照区块的顺序将每个区块星星个数排成一序列a，那么a[1]<a[2]<…<a[n-1]<a[n]，a[1]=1.而且每个区块的星星的个数a[k]都等于其他两个区块a[i]和a[j]的星星个数的和；(1<=i<=j<=n)
他尝试着将a[n]作为最后一项，构造一个也满足a[k]=a[i]+a[j]的序列l，结果得到的序列l的长度无论如何都比星星个数构成的序列a长，现在QuQ想考考你，他把a[n]告诉你，你得想办法找出星星序列a，要求使每个数尽量大。

Format

Input

共一行,只有一个整数a[n]，即星星构成的序列的最后一项

Output

第一行是输出一个整数n，表示序列中的元素个数；
第二行输出数列，每两个数之间有且只有一个空格.

Sample 1

Input

4

Output

3
1 2 4

Limitation

Time Limit: 1000 MS

Memory Limit: 256000 K
Allow Language: Pascal , CPP ,C

Hint

对于80%的数据，1<=n<=1000；
对于100%的数据， 1<=n<=1500.

注：改自《国际大学生程序设计竞赛例题解数论、计算几何、搜索算法专集 2006》P 229 神奇的数列

版权归原作者所有