CF2180C.XOR-factorization

Ostad thinks that the usual way of factoring numbers is too mathematical, so he invented a new notion called XOR-factorization, which is more computer-science-like. For a given integer $n$, a sequence of integers $a_1, a_2, \ldots, a_k$ with $0 \le a_i \le n$ for all $i$ is called a XOR-factorization of $n$ if and only if $$ a_1 \oplus a_2 \oplus \cdots \oplus a_k = n, $$ where $\oplus$ denotes the bitwise XOR operation.

You are given integers $n$ and $k$. Find a XOR-factorization $a_1, a_2, \ldots, a_k$ of $n$ that maximizes the sum $a_1 + a_2 + \cdots + a_k$.

It can be proven that under the problem conditions, a XOR-factorization always exists.

奥斯塔德认为，传统的因数分解方式过于数学化，因此他发明了一种名为“异或分解（XOR-factorization）”的新概念，该概念更具计算机科学特色。对于给定的整数 $n$，若一个整数序列 $a_1, a_2, \ldots, a_k$ 满足对所有 $i$ 都有 $0 \le a_i \le n$，且

$$a\_1 \\oplus a\_2 \\oplus \\cdots \\oplus a\_k = n,$$

则称该序列为 $n$ 的一个异或分解，其中 $\oplus$ 表示按位异或运算。

现给你两个整数 $n$ 和 $k$。请找出 $n$ 的一个异或分解 $a_1, a_2, \ldots, a_k$，使得其元素之和 $a_1 + a_2 + \cdots + a_k$ 最大。

在本题约束条件下，可以证明异或分解一定存在。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

Each of the next $t$ lines contains two integers $n$ and $k$ ($1 \le n \le 10^9$, $1 \le k \le 10^5$).

It is guaranteed that the sum of $k$ over all test cases does not exceed $10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是测试用例的描述。

接下来的 $t$ 行中，每行包含两个整数 $n$ 和 $k$（$1 \le n \le 10^9$，$1 \le k \le 10^5$）。

保证所有测试用例中 $k$ 的总和不超过 $10^5$。

For each test case, output $k$ integers $a_1, a_2, \ldots, a_k$ such that $0 \le a_i \le n$.

We can show that an answer always exists. If there are multiple valid answers, you may print any of them in any order.

对于每个测试用例，输出 $k$ 个整数 $a_1, a_2, \ldots, a_k$，满足 $0 \le a_i \le n$。

可以证明答案一定存在。如果存在多个合法的答案，你可以以任意顺序输出其中任意一个。

In the first test case, we can factor $5$ as $1 \oplus 4 \oplus 5 \oplus 5$ with a sum of $15$, and it can be shown that no other XOR-factorization has a higher sum.

In the second test case, we can factor $4$ as $4 \oplus 4 \oplus 4$ with a sum of $12$, which is trivially the maximum possible.

在第一个测试用例中，我们可以将 $5$ 分解为 $1 \oplus 4 \oplus 5 \oplus 5$，其和为 $15$，且可以证明不存在其他异或分解方式能得到更高的和。

在第二个测试用例中，我们可以将 $4$ 分解为 $4 \oplus 4 \oplus 4$，其和为 $12$，这显然是可能的最大值。