配点 : $1000$ 点

問題文

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

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

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

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

• $1 \leq |s| \leq 200$
• $s$ は $1$ から $100$ までの整数で表される $100$ 種類の文字のみからなる。
• $s$ の $2^{|s|}$ 個ある部分列のうち、良い文字列であるようなものは $N$ 個ある。

制約

• $1 \leq N \leq 10^{12}$

入力

入力は以下の形式で標準入力から与えられる。

$N$

出力

$1$ 行目には $s$ の長さ $|s|$ を出力せよ。 $2$ 行目に $s$ の各要素を $1$ 文字目から順に空白区切りで出力せよ。$s$ が上記の条件を満たすならば正解となる。

7

4
1 1 1 1

$s$ の部分列であって良い文字列となるようなものは (1,1) と (1,1,1,1) の $2$ 種類があります。(1,1) であるような部分列は $6$ 個、(1,1,1,1) であるような部分列は $1$ 個あるため、合計 $7$ 個です。

299

23
32 11 11 73 45 8 11 83 83 8 45 32 32 10 100 73 32 83 45 73 32 11 10