Description

Lately, the cows on Farmer John's farm have been infatuated with watching the show Apothecowry Dairies. The show revolves around a clever bovine sleuth CowCow solving problems of various kinds. Bessie found a new problem from the show, but the solution won't be revealed until the next episode in a week! Please solve the problem for her.

You are given integers $M$ and $K$ $(1 \leq M \leq 10 ^ 9, 1 \leq K \leq 31)$. Please choose a positive integer $N$ and construct a sequence $a$ of $N$ non-negative integers such that the following conditions are satisfied:

• $1 \le N \le 100$
• $a_1 + a_2 + \dots + a_N = M$
• $\text{popcount}(a_1) \oplus \text{ popcount}(a_2) \oplus \dots \oplus \text{ popcount}(a_N) = K$

If no such sequence exists, print $-1$.

$\dagger \text{ popcount}(x)$ is the number of bits equal to $1$ in the binary representation of the integer $x$. For instance, the popcount of $11$ is $3$ and the popcount of $16$ is $1$.

$\dagger \oplus$ is the bitwise xor operator.

The input will consist of $T$ ($1 \le T \le 5 \cdot 10^3$) independent test cases.

Input Format

The first line contains $T$.

The first and only line of each test case has $M$ and $K$.

It is guaranteed that all test cases are unique.

Output Format

Output the solutions for $T$ test cases as follows:

If no answer exists, the only line for that test case should be $-1$.

Otherwise, the first line for that test case should be a single integer $N$, the length of the sequence -- ($1 \le N \le 100$).

The second line for that test case should contain $N$ space-separated integers that satisfy the conditions -- ($0 \le a_i \le M$).

3
2 1
33 5
10 5

2
2 0
3
3 23 7 
-1

Hint

In the first test case, the elements in the array $a = [2, 0]$ sum to $2$. The xor sum of popcounts is $1 \oplus 0 = 1$. Thus, all the conditions are satisfied.

In the second test case, the elements in the array $a = [3, 23, 7]$ sum to $33$. The xor sum of the popcounts is $2 \oplus 4 \oplus 3 = 5$. Thus, all conditions are satisfied.

Other valid arrays are $a = [4, 2, 15, 5, 7]$ and $a = [1, 4, 0, 27, 1]$.

It can be shown that no valid arrays exist for the third test case.

SCORING:

• Input 2: $M \leq 8, K \leq 8$
• Inputs 3-5: $M \gt 2^K$
• Inputs 6-18: No additional constraints.