← 返回题目列表

Codeforces · 1810/B

B. 糖果

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

这个问题是关于糖果的。最初,您只有 $$$1$$$ 糖果,并且您想要恰好有 $$$n$$$ 糖果。

你可以以任意顺序使用以下两个咒语,总共最多 $$$40$$$ 次。

- 假设你现在有 $$$x$$$ 糖果。如果你使用第一个咒语,那么 $$$x$$$ 糖果会变成 $$$2x-1$$$ 糖果。
- 假设你现在有 $$$x$$$ 糖果。如果你使用第二个咒语,那么$$$x$$$糖果就会变成$$$2x+1$$$糖果。

构建一系列咒语,以便按顺序使用它们后,您将恰好获得 $$$n$$$ 糖果,或者确定这是不可能的。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。他们的描述如下。

每个测试用例都包含一行,其中包含一个整数 $$$n$$$ ($$$2 \le n \le 10^9$$$) — 所需的最终糖果数量。

输出

对于每个测试用例,输出以下内容。

如果最终有可能在 $$$40$$$ 咒语内获得 $$$n$$$ 糖果,请在第一行打印一个整数 $$$m$$$ ($$$1 \le m \le 40$$$),代表你使用的咒语总数。

在第二个打印中 $$$m$$$ 整数 $$$a_{1}, a_{2}, \ldots, a_{m}$$$ ($$$a_{i}$$$ 是 $$$1$$$ 或 $$$2$$$)以空格分隔,其中 $$$a_{i} = 1$$$ 表示您使用了第 $$$i$$$ 步骤,而 $$$a_{i} = 2$$$ 表示您在第 $$$i$$$ 步骤中使用第二个咒语。

请注意,您不必最小化$$$m$$$,如果有多个解决方案,您可以输出其中任何一个。

如果不可能,则一行输出$$$-1$$$。

示例

输入 #1

4
2
3
7
17

输出 #1

-1
1
2 
2
2 2 
4
2 1 1 1

注意

对于$$$n=3$$$,你可以只使用第二个咒语一次,然后得到$$$2 \cdot 1 + 1 = 3$$$糖果。

对于$$$n=7$$$,你可以使用第二个咒语两次。完成第一步后,您将获得 $$$3$$$ 糖果。第二步之后,您将获得 $$$2 \cdot 3 + 1 = 7$$$ 糖果。