| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 114 | 49 | 43 | 44.792% |
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:
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.
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 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
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.