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

입력

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

출력

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.

제한

노트

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.