/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
文字列 x が以下の条件を満たすとき、x を 良い文字列 と呼びます。
- 条件：x はある長さ 1 以上の文字列 y を 2 回繰り返した文字列 yy で表すことができる。
例えば aa,bubobubo などは良い文字列ですが、空文字列、a,abcabcabc,abba などは良い文字列ではありません。
ワシとフクロウが良い文字列に関するパズルを作りました。 以下の条件を満たす文字列 s をどれか 1 つ求めてください。この問題の制約下で、そのような文字列が必ず存在することが証明できます。
- 1 ≦ |s| ≦ 200
- s は 1 から 100 までの整数で表される 100 種類の文字のみからなる。
- s の 2^{|s|} 個ある部分列のうち、良い文字列であるようなものは N 個ある。
制約
- 1 ≦ N ≦ 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
1 行目には s の長さ |s| を出力せよ。 2 行目に s の各要素を 1 文字目から順に空白区切りで出力せよ。s が上記の条件を満たすならば正解となる。
入力例 1
7
出力例 1
4 1 1 1 1
s の部分列であって良い文字列となるようなものは (1,1) と (1,1,1,1) の 2 種類があります。(1,1) であるような部分列は 6 個、(1,1,1,1) であるような部分列は 1 個あるため、合計 7 個です。
入力例 2
299
出力例 2
23 32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10
Score : 1000 points
Problem Statement
We will call a string x good if it satisfies the following condition:
- Condition: x can be represented as a concatenation of two copies of another string y of length at least 1.
For example, aa and bubobubo are good; an empty string, a, abcabcabc and abba are not good.
Eagle and Owl created a puzzle on good strings. Find one string s that satisfies the following conditions. It can be proved that such a string always exists under the constraints in this problem.
- 1 ≤ |s| ≤ 200
- Each character of s is one of the 100 characters represented by the integers 1 through 100.
- Among the 2^{|s|} subsequences of s, exactly N are good strings.
Constraints
- 1 ≤ N ≤ 10^{12}
Input
Input is given from Standard Input in the following format:
N
Output
In the first line, print |s|, the length of s. In the second line, print the elements in s in order, with spaces in between. Any string that satisfies the above conditions will be accepted.
Sample Input 1
7
Sample Output 1
4 1 1 1 1
There are two good strings that appear as subsequences of s: (1,1) and (1,1,1,1). There are six occurrences of (1,1) and one occurrence of (1,1,1,1), for a total of seven.
Sample Input 2
299
Sample Output 2
23 32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10