8646: The Dark Temple

Illidan is practicing light magic now and he is trying to use holy light to make a good tree.

A good tree is a rooted tree and each vertex of it is either a leaf or has two children.

And he wants the sum of the depth of each vertex in the tree to be a certain number. The depth of a vertex is the length of the path to its root.

The "depth sequence" A of tree T, is an infinite sequence where A[i] = f(T,i)f(T, i) is the number of vertices in the tree $T$ with depth $i$.

Given an integer k, you should determine whether there is a good tree T such that,

i≥0∑f(T,i)∗i=k

If there is no such tree, output -1.

If there are more than one eligible trees, please output the one with the minimum number of vertices.

If there are still more than one eligible trees, please output the one with the lexicographically smallest depth sequence.

In this problem, for your convenience, you only need to output the depth sequence of the tree.

It can be proven that the output is uniquely determined.

Note: For two infinite sequences $A$ and $B$, $A$ is less than $B$ in lexicographical order if and only if there exists i$\ge 0$ such that $A[i]<B[i]$, and A[j] =B[j] for all j =0..i-1

The input consists of multiple test cases.

The first line contains one integer $(1\le T\le 10)$ denoting the number of test cases.

The following are T test cases.

Each test case consists of one line containing one integer k (0≤k≤1012), which is the sum of depth of all vertices.

For each test case, if there is no such tree, output one line containing -1.

Otherwise, output two lines.

The first line contains two numbers n and $d$ indicating the number of vertices and the maximal depth of vertices in the tree.

The second line contains d + 1 numbers indicating A[0]..A[d] that is the positive part of the degree sequence A.