Background

Little U is very interested in functions that map a set to a number, and $\text{mex}$ is a good example.

$\text{mex}(S)$ means the smallest non-negative integer that does not appear in the set $S$.

Problem Description

Multiple test cases.

For each test case, given $c$, you need to construct a sequence $a_1,a_2,...,a_n\in [0,2\times 10^9]$ such that

$$\sum\limits_{S\neq \emptyset,S\subseteq \{1,2,...,n\}}\text{mex}(a_{S_1},a_{S_2},...,a_{S_{|S|}})=c$$

where $1\le n\le 40$ is required. It can be proven that within the constraints of this problem, if a solution exists, then a solution must exist for some $1\le n\le 40$.

Input Format

The first line contains an integer $T$, the number of test cases.

Then there are $T$ lines, each containing a non-negative integer $c$.

Output Format

For each test case:

If there is no solution, output only one line with an integer $-1$.

Otherwise, output a positive integer $n$ on the first line.

Output $n$ non-negative integers $a_1,a_2,...,a_n$ on the second line.

5
120
8128
248
0
5

7
1 9 1 9 8 1 0
13
1 1 4 5 1 4 1 9 1 9 8 1 0
8
1 2 3 9 0 7 3 8
7
1 2 3 9 7 3 8
-1

Hint

Sample Explanation

I have a wonderful explanation, but unfortunately it cannot fit here.

Constraints

$id$ is the $\text{subtask}$ index.

$id$	Special Property	Score	$id$	Special Property	Score
$1$	$c\le10$	$3$	$6$	$c\le1\times 10^6$	$15$
$2$	$c\le30$	$6$	$7$	$T\le 10$	$5$
$3$	$c\le500$		$8$	$T\le 5\times 10^4$	$15$
$4$	$c\le2\times 10^3$	$5$	$9$	$T\le 8\times 10^4$	$10$
$5$	$c\le1\times 10^5$	$20$	$10$		$15$

For $100\%$ of the testdata, $T\le 10^5$, $0\le c\le 2\times 10^9$.

Tips

Because the constants of some STL implementations are large, if you believe your time complexity is fine but you get TLE, please do not use STL.

Please pay attention to output efficiency. Here is a fast output template (please do not use the code below to output negative numbers):

void write(int x){
	if(x>9)write(x/10);
	putchar(x%10+'0');
}

Translated by ChatGPT 5