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.

#8415 upload 2 done - how_to_reg -

Sequence Construction timer 1s memory 1024MB

#8415

Sequence Construction 1s 1024MB