← 返回题目列表

Codeforces · 2180/C

C. 异或分解

中文机器翻译题面 查看原题

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$$$。

我们可以证明答案总是存在的。如果有多个有效答案,您可以按任何顺序打印其中任何一个。

示例

输入
复制

4
5 4
4 3
8 2
1 1

输出
复制

1 4 5 5
4 4 4
0 8
1

注意

在第一个测试用例中,我们可以将$$$5$$$分解为$$$1 \oplus 4 \oplus 5 \oplus 5$$$,总和为$$$15$$$,并且可以证明没有其他 异或分解 的总和更高。

在第二个测试用例中,我们可以将 $$$4$$$ 分解为 $$$4 \oplus 4 \oplus 4$$$,总和为 $$$12$$$,这通常是可能的最大值。