AtCoder Grand Contest 012

C - Tautonym Puzzle


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

配点 : 1000

問題文

文字列 x が以下の条件を満たすとき、x良い文字列 と呼びます。

  • 条件:x はある長さ 1 以上の文字列 y2 回繰り返した文字列 yy で表すことができる。

例えば aa,bubobubo などは良い文字列ですが、空文字列、a,abcabcabc,abba などは良い文字列ではありません。

ワシとフクロウが良い文字列に関するパズルを作りました。 以下の条件を満たす文字列 s をどれか 1 つ求めてください。この問題の制約下で、そのような文字列が必ず存在することが証明できます。

  • 1 ≦ |s| ≦ 200
  • s1 から 100 までの整数で表される 100 種類の文字のみからなる。
  • s2^{|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

Submit提出する