← 返回题目列表

Codeforces · 1348/D

D. 凤凰与科学

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

菲尼克斯决定成为一名科学家!他目前正在研究细菌的生长。

最初,在 $$$1$$$ 天,有一种细菌,质量为 $$$1$$$。

每天都会有一定数量的细菌分裂(可能为零或全部)。当一个质量为 $$$m$$$ 的细菌分裂时,它会变成两个质量为 $$$\frac{m}{2}$$$ 的细菌。例如,质量为 $$$3$$$ 的细菌可以分裂为质量为 $$$1.5$$$ 的两个细菌。

而且,每到夜晚,每种细菌的质量都会增加一倍。

Phoenix 想知道所有细菌的总质量是否有可能恰好为 $$$n$$$。如果可能的话,他对如何使用尽可能少的夜晚数获得该质量感兴趣。帮助他成为最好的科学家!

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^9$$$) - Phoenix 感兴趣的细菌质量总和。

输出

对于每个测试用例,如果细菌无法精确达到总质量 $$$n$$$,则打印 -1。否则,打印两行。

第一行应包含一个整数 $$$d$$$ — 所需的最少住宿天数。

下一行应包含 $$$d$$$ 整数,其中第 $$$i$$$ 整数表示应在第 $$$i$$$ 天分裂的细菌数量。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

3
9
11
2

输出 #1

3
1 0 2 
3
1 1 2
1
0

注意

在第一个测试用例中,以下过程会产生总质量为 $$$9$$$ 的细菌:

- 天 $$$1$$$:质量为 $$$1$$$ 的细菌分裂。现在有两种细菌,每种细菌的质量为 $$$0.5$$$。
- 夜晚$$$1$$$:所有细菌的质量增加一。现在有两种质量为 $$$1.5$$$ 的细菌。
- Day $$$2$$$:无分割。
- 夜晚 $$$2$$$:现在有两种质量为 $$$2.5$$$ 的细菌。
- Day $$$3$$$:两种细菌分裂。现在有四种细菌,质量为 $$$1.25$$$。
- 夜晚$$$3$$$:现在有四种细菌,质量为$$$2.25$$$。

$$$ $$$

在第二个测试用例中,以下过程会产生总质量为 $$$11$$$ 的细菌:

- 天 $$$1$$$:质量为 $$$1$$$ 的细菌分裂。现在有两种质量为 $$$0.5$$$ 的细菌。
- 夜晚 $$$1$$$:现在有两种质量为 $$$1.5$$$ 的细菌。
- Day $$$2$$$:一种细菌分裂。现在存在三种质量为 $$$0.75$$$、$$$0.75$$$ 和 $$$1.5$$$ 的细菌。
- 夜间 $$$2$$$:现在存在三种质量为 $$$1.75$$$、$$$1.75$$$ 和 $$$2.5$$$ 的细菌。
- 天 $$$3$$$:质量为 $$$1.75$$$ 的细菌和质量为 $$$2.5$$$ 的细菌分裂。现在有五种细菌,其质量为 $$$0.875$$$、$$$0.875$$$、$$$1.25$$$、$$$1.25$$$ 和 $$$1.75$$$。
- 夜间 $$$3$$$:现在有五种具有质量的细菌 $$$1.875$$$、$$$1.875$$$、$$$2.25$$$、$$$2.25$$$ 和 $$$2.75$$$。

$$$ $$$

在第三个测试案例中,细菌在 $$$1$$$ 当天不分裂,然后在夜间 $$$1$$$ 生长为质量 $$$2$$$。