CF1453D.Checkpoints

Gildong is developing a game consisting of $n$ stages numbered from $1$ to $n$. The player starts the game from the $1$-st stage and should beat the stages in increasing order of the stage number. The player wins the game after beating the $n$-th stage.

There is at most one checkpoint on each stage, and there is always a checkpoint on the $1$-st stage. At the beginning of the game, only the checkpoint on the $1$-st stage is activated, and all other checkpoints are deactivated. When the player gets to the $i$-th stage that has a checkpoint, that checkpoint is activated.

For each try of a stage, the player can either beat the stage or fail the stage. If they beat the $i$-th stage, the player is moved to the $i+1$-st stage. If they fail the $i$-th stage, the player is moved to the most recent checkpoint they activated, and they have to beat the stages after that checkpoint again.

For example, assume that $n = 4$ and the checkpoints are on the $1$-st and $3$-rd stages. The player starts at the $1$-st stage. If they fail on the $1$-st stage, they need to retry the $1$-st stage because the checkpoint on the $1$-st stage is the most recent checkpoint they activated. If the player beats the $1$-st stage, they're moved to the $2$-nd stage. If they fail it, they're sent back to the $1$-st stage again. If they beat both the $1$-st stage and the $2$-nd stage, they get to the $3$-rd stage and the checkpoint on the $3$-rd stage is activated. Now whenever they fail on the $3$-rd stage, or the $4$-th stage after beating the $3$-rd stage, they're sent back to the $3$-rd stage. If they beat both the $3$-rd stage and the $4$-th stage, they win the game.

Gildong is going to build the stages to have equal difficulty. He wants you to find any series of stages and checkpoints using at most $2000$ stages, where the expected number of tries over all stages is exactly $k$, for a player whose probability of beating each stage is exactly $\cfrac{1}{2}$.

吉尔东正在开发一款包含 $n$ 个关卡的游戏，关卡编号从 $1$ 到 $n$。玩家从第 $1$ 关开始游戏，并需按关卡编号递增的顺序依次通关。玩家在成功通关第 $n$ 关后获胜。

每个关卡上最多设置一个检查点（checkpoint），且第 $1$ 关必定设有检查点。游戏开始时，仅有第 $1$ 关的检查点处于激活状态，其余所有检查点均未激活。当玩家到达第 $i$ 关且该关设有检查点时，该检查点即被激活。

每次尝试通关某一关时，玩家要么成功通关，要么失败。若玩家成功通关第 $i$ 关，则进入第 $i+1$ 关；若玩家在第 $i$ 关失败，则返回至其最近一次激活的检查点所在关卡，并需重新通关该检查点之后的所有关卡。

例如，设 $n = 4$，且检查点位于第 $1$ 关和第 $3$ 关。玩家起始于第 $1$ 关：

• 若在第 $1$ 关失败，则因第 $1$ 关是其唯一已激活的检查点，故需重试第 $1$ 关；
• 若成功通关第 $1$ 关，则进入第 $2$ 关；
• 若在第 $2$ 关失败，则仍返回至第 $1$ 关重试；
• 若连续成功通关第 $1$ 关与第 $2$ 关，则抵达第 $3$ 关，此时第 $3$ 关的检查点被激活；
• 此后，若在第 $3$ 关失败，或在通关第 $3$ 关后于第 $4$ 关失败，均将返回至第 $3$ 关；
• 若连续成功通关第 $3$ 关与第 $4$ 关，则游戏胜利。

吉尔东计划将所有关卡设计为难度相同。他希望你构造一组关卡及检查点配置（关卡总数不超过 $2000$），使得对于每关通关概率恰好为 $\cfrac{1}{2}$ 的玩家，其在整个游戏中所有关卡的尝试次数的期望值（期望值）恰好等于 $k$。

Each test contains one or more test cases. The first line contains the number of test cases $t$ ($1 \le t \le 50$).

Each test case contains exactly one line. The line consists of a single integer $k$ ($1 \le k \le 10^{18}$) — the expected number of tries over all stages Gildong wants to set for a player whose probability of beating each stage is exactly $\cfrac{1}{2}$.

每个测试包含一个或多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 50$）。

每个测试用例恰好包含一行。该行包含一个整数 $k$（$1 \le k \le 10^{18}$）——即吉隆希望为一名每关通关概率恰好为 $\cfrac{1}{2}$ 的玩家所设定的、所有关卡的期望尝试次数总和。

For each test case, print $-1$ if it's impossible to construct such a series of stages and checkpoints using at most $2000$ stages.

Otherwise, print two lines. The first line should contain a single integer $n$ ($1 \le n \le 2000$) – the number of stages. The second line should contain $n$ integers, where the $i$-th integer represents whether the $i$-th stage has a checkpoint. The $i$-th integer should be $0$ if the $i$-th stage doesn't have a checkpoint, and $1$ if it has a checkpoint. Note that the first integer must be $1$ according to the description.

对于每个测试用例，如果无法使用至多 $2000$ 个关卡构造出满足要求的关卡与检查点序列，则输出 $-1$。

否则，输出两行。第一行应包含一个整数 $n$（$1 \le n \le 2000$），表示关卡数量。第二行应包含 $n$ 个整数，其中第 $i$ 个整数表示第 $i$ 个关卡是否设有检查点：若第 $i$ 个关卡没有检查点，则该整数为 $0$；若有检查点，则为 $1$。注意，根据题意，第一个整数必须为 $1$。

In the first and the second case, we can see that the 'easiest' series of stages is to have $1$ stage with a checkpoint. This already requires $2$ tries in expectation, so it is impossible to make it to require only $1$ try.

In the third case, it takes $2$ tries in expectation to beat each stage, and the player can always retry that stage without falling back to one of the previous stages if they fail it. Therefore the total expected number of tries is $8$. Note that there exists an answer with fewer stages, but you are not required to minimize the number of stages used.

在第一种和第二种情况下，我们可以看出，“最简单”的关卡序列是设置 $1$ 个带存档点的关卡。这本身已需要期望 $2$ 次尝试，因此不可能使期望尝试次数仅为 $1$ 次。

在第三种情况下，每一关期望需要 $2$ 次尝试才能通过，且玩家在失败时总能重新挑战该关卡，而无需回退到前面任意一关。因此，总的期望尝试次数为 $8$。注意，存在使用更少关卡的方案，但你无需最小化所用关卡的数量。