Page not loading? Try clicking here.
Placeholder

#8415

Sequence Construction 1s 1024MB

Problems

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

The first line contains an integer T (1 \le T \le 5\cdot10^3), the number of test cases.

Each of the following T test cases is given on a single line containing two space-separated integers M and K.


Output

On the first line, a single integer N (1 \le N \le 100), the length of the sequence.

On the second line, N space-separated integers a_1, a_2, \dots, a_N (0 \le a_i \le M) representing the sequence. If no such sequence exists, output -1 on a single line for that test case.


Example 

3
2 1
33 5
10 5
2
2 0
3
3 23 7
-1

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.


Source

USACO 2025 US Open Silver

You must sign in to write code.