← 返回题目列表

AtCoder · agc012_c

C. Tautonym 谜题

中文机器翻译题面 查看原题

分数: 1000 点

问题陈述

我们将调用一个字符串 x 好 如果满足以下条件:

  • 条件: x 可以表示为另一个字符串的两个副本的串联 长度至少为 y 至少长度 1.

例如, aa 和 bubobubo 都很好;一个空字符串, a, abcabcabc 和 abba 不好。

老鹰和猫头鹰用好绳子创造了一个谜题。 找到一个字符串 s 满足以下条件。可以证明,在本问题的约束下,这样的字符串总是存在的。

  • 1 ≤ |s| ≤ 200
  • 每个字符 s 是其中之一 100 整数表示的字符 1 通过 100.
  • 其中 2^{|s|} 的子序列 s,正是 N 是很好的字符串。

约束

  • 1 ≤ N ≤ 10^{12}

输入

输入由标准输入按以下格式给出:

N

输出

在第一行中,打印 |s|,长度 s。 在第二行中,打印其中的元素 s 按顺序排列,中间有空格。任何满足上述条件的字符串都将被接受。


示例输入 1

7

示例输出 1

4
1 1 1 1

有两个好的字符串作为以下序列出现 s: (1,1) 和 (1,1,1,1)。有六次出现 (1,1) 并且出现一次 (1,1,1,1),总共七个。


示例输入 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