Ostad 认为通常的因式分解方法过于数学化,因此他发明了一个新概念,称为 异或分解,这更像计算机科学。对于给定的整数 $$$n$$$,所有 $$$i$$$ 的整数序列 $$$a_1, a_2, \ldots, a_k$$$ 以及 $$$0 \le a_i \le n$$$ 称为 a $$$n$$$ 的 异或分解 当且仅当 $$a_1 \oplus a_2 \oplus \cdots \oplus a_k = n,$$ 其中 $$$\oplus$$$ 表示按位异或运算。
给定整数 $$$n$$$ 和 $$$k$$$。寻找一个 异或分解 $$$a_1, a_2, \ldots, a_k$$$ 的 $$$n$$$ 最大化总和 $$$a_1 + a_2 + \cdots + a_k$$$。
可以证明,在问题条件下, 异或分解 始终存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出 $$$k$$$ 整数 $$$a_1, a_2, \ldots, a_k$$$ 使得 $$$0 \le a_i \le n$$$。
我们可以证明答案总是存在的。如果有多个有效答案,您可以按任何顺序打印其中任何一个。
示例
输入复制
45 44 38 21 1
输出复制
1 4 5 54 4 40 81
注意
在第一个测试用例中,我们可以将$$$5$$$分解为$$$1 \oplus 4 \oplus 5 \oplus 5$$$,总和为$$$15$$$,并且可以证明没有其他 异或分解 的总和更高。
在第二个测试用例中,我们可以将 $$$4$$$ 分解为 $$$4 \oplus 4 \oplus 4$$$,总和为 $$$12$$$,这通常是可能的最大值。