Sequence Construction
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≤M≤109,1≤K≤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≤N≤100
- a1+a2+⋯+aN=M
- popcount(a1)⊕ popcount(a2)⊕⋯⊕ popcount(aN)=K
If no such sequence exists, print −1.
† 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.
†⊕ is the bitwise xor operator.
The input will consist of T (1≤T≤5⋅103) independent test cases.
In the first test case, the elements in the array a=[2,0] sum to 2. The xor sum of popcounts is 1⊕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⊕4⊕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≤8,K≤8
- Inputs 3-5: M>2K
- Inputs 6-18: No additional constraints.
Problem credits: Aakash Gokhale
Source: USA Computing Olympiad.
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≤N≤100).
The second line for that test case should contain N space-separated integers that satisfy the conditions -- (0≤ai≤M).