Checkpoints
Contest: Codeforces Round 688 (Div. 2)
Difficulty rating: 1900
Tags: brute force, constructive algorithms, greedy, math, probabilities

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}$$$.

Input format:
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}$$$.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 512.0 MB

Note:
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.

Example input:
4
1
2
8
12

Example output:
-1
1
1
4
1 1 1 1
5
1 1 0 1 1

Editorial:
As already explained in the notes (and is quite obvious), the expected number of tries to beat stage $$$i$$$ with a checkpoint where stage $$$i+1$$$ also has a checkpoint (or is the end of the game) is $$$2$$$. What if stage $$$i+1$$$ doesn't have a checkpoint and stage $$$i+2$$$ has a checkpoint?
We can think of it like this. It takes $$$2$$$ tries in expectation to get to stage $$$i+1$$$, and the player needs to add one more try, trying $$$3$$$ times in total. But this also has a probability of $$$\cfrac{1}{2}$$$ to succeed, so the expected number of tries to actually get to stage $$$i+2$$$ is multiplied by $$$2$$$ – making it $$$6$$$ in total.
This can be extended indefinitely. Let's say $$$x_i$$$ is the expected number of tries to beat $$$i$$$ consecutive stages with only one checkpoint at the beginning. If we extend it to $$$i+1$$$ consecutive stages, it takes $$$x_{i+1} = 2 \cdot (x_i+1)$$$ tries. If this is not intuitive, we can always use Monte Carlo method to simulate how many tries each takes. The general term for this sequence is $$$x_i = 2^{i+1} - 2$$$, and it is introduced in OEIS A000918 with a similar example.
As each checkpoint makes the stages after that checkpoint independent of the previous stages, we can just add up appropriate $$$x_i$$$'s to make it equal to $$$k$$$. Using $$$x_i$$$ means we append the stages in $$$1$$$ $$$0$$$ $$$0$$$ $$$0$$$ ... form where the number of $$$0$$$'s is $$$i-1$$$.
As every term of the sequence is even, the answer is $$$-1$$$ if $$$k$$$ is odd. Otherwise, we can show that there always exists an answer for all even $$$k \le 10^{18}$$$. There are two simple strategies to make it with at most $$$2000$$$ stages.
The first strategy is to greedily take the greatest $$$x_i \le y$$$ where $$$y$$$ is the remaining number, then append $$$x_i$$$ and subtract it from $$$y$$$. This works because either $$$y$$$ can be exactly $$$2 \cdot x_i$$$, or we can use $$$x_i$$$ once and repeat the process with $$$y-x_i$$$. The worst case for this strategy is to use all of $$$x_{57}$$$, $$$x_{56}$$$, $$$x_{55}$$$, ..., $$$x_1$$$ and another $$$x_1$$$, which sums up to total of $$$1654$$$ stages.
Another strategy is to use $$$x_i$$$ and $$$x_1$$$ if bit $$$i+1$$$ ($$$0$$$-indexed) is $$$1$$$. Since there can be at most $$$58$$$ $$$1$$$-bits, the worst case for this strategy is still far less than $$$2000$$$.
Time complexity: $$$\mathcal{O}(\log^2{k})$$$