Gildong 正在开发一款由 $$$n$$$ 阶段组成的游戏,阶段编号从 $$$1$$$ 到 $$$n$$$。玩家从 $$$1$$$-st 阶段开始游戏,并应按照阶段编号递增的顺序击败阶段。玩家在完成第 $$$n$$$ 关卡后赢得游戏。
每个阶段最多有一个检查点,并且第 $$$1$$$-st 阶段始终有一个检查点。游戏开始时,只有$$$1$$$-st阶段的检查点被激活,所有其他检查点都被停用。当玩家到达有检查点的第 $$$i$$$ 阶段时,该检查点将被激活。
对于每个阶段的尝试,玩家可以通过该阶段或失败该阶段。如果他们击败了第 $$$i$$$ 阶段,则玩家将移动到第 $$$i+1$$$ 阶段。如果他们在第$$$i$$$阶段失败,玩家将被移动到他们激活的最近的检查点,并且他们必须再次通过该检查点之后的阶段。
例如,假设 $$$n = 4$$$ 并且检查点位于 $$$1$$$-st 和 $$$3$$$-rd 阶段。玩家从 $$$1$$$-st 阶段开始。如果他们在 $$$1$$$-st 阶段失败,他们需要重试 $$$1$$$-st 阶段,因为 $$$1$$$-st 阶段上的检查点是他们激活的最近检查点。如果玩家击败了 $$$1$$$-st 阶段,他们就会进入 $$$2$$$-nd 阶段。如果他们失败了,他们会再次被送回 $$$1$$$-st 阶段。如果他们同时击败了 $$$1$$$-st 阶段和 $$$2$$$-nd 阶段,他们将到达 $$$3$$$-rd 阶段,并且 $$$3$$$-rd 阶段上的检查点被激活。现在,只要他们在 $$$3$$$-rd 阶段失败,或者在击败 $$$3$$$-rd 阶段后在 $$$4$$$-th 阶段失败,他们就会被送回 $$$3$$$-rd 阶段。如果他们同时击败了 $$$3$$$-rd 阶段和 $$$4$$$-th 阶段,他们就赢得了比赛。
Gildong 将建造具有相同难度的舞台。他希望您使用最多 $$$2000$$$ 阶段来找到任何系列阶段和检查点,其中所有阶段的预期尝试次数恰好为 $$$k$$$,对于击败每个阶段的概率恰好为 $$$\cfrac{1}{2}$$$ 的玩家来说。
输入
每个测试都包含一个或多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 50$$$)。
每个测试用例仅包含一行。该行由一个整数 $$$k$$$ ($$$1 \le k \le 10^{18}$$$) 组成 - Gildong 想要为击败每个阶段的概率恰好为 $$$\cfrac{1}{2}$$$ 的玩家设置的所有阶段的预期尝试次数。
输出
对于每个测试用例,如果无法使用最多 $$$2000$$$ 阶段构建这样一系列阶段和检查点,则打印 $$$-1$$$ 。
否则,打印两行。第一行应包含一个整数 $$$n$$$ ($$$1 \le n \le 2000$$$) – 阶段数。第二行应包含 $$$n$$$ 整数,其中第 $$$i$$$ 个整数表示第 $$$i$$$ 个阶段是否有检查点。如果第 $$$i$$$ 个阶段没有检查点,则第 $$$i$$$ 个整数应为 $$$0$$$;如果有检查点,则应为 $$$1$$$。请注意,根据描述,第一个整数必须是 $$$1$$$。
示例
输入 #1
4 1 2 8 12
输出 #1
-1 1 1 4 1 1 1 1 5 1 1 0 1 1
注意
在第一种和第二种情况中,我们可以看到“最简单”的一系列阶段是具有带有检查点的 $$$1$$$ 阶段。这已经需要 $$$2$$$ 尝试,所以不可能让它只需要 $$$1$$$ 尝试。
在第三种情况下,需要 $$$2$$$ 尝试来击败每个阶段,并且玩家可以随时重试该阶段,而不会在失败时退回到之前的阶段之一。因此,预计总尝试次数为 $$$8$$$。请注意,存在一个阶段较少的答案,但您不需要最小化所使用的阶段数。