← 返回题目列表

Codeforces · 1965/B

B. 缺失子序列和

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

给你两个整数 $$$n$$$ 和 $$$k$$$。查找大小最多为 $$$25$$$ 的非负整数序列 $$$a$$$ ,使得以下条件成立。

- $$$a$$$ 不存在总和为 $$$k$$$ 的子序列。
- 对于所有 $$$1 \le v \le n$$$ 其中 $$$v \ne k$$$,存在 $$$a$$$ 的子序列,总和为 $$$v$$$。

序列 $$$b$$$ 是 $$$a$$$ 的子序列,如果 $$$b$$$ 可以通过删除几个(可能是零个或全部)元素从 $$$a$$$ 获得,而不改变剩余元素的顺序。例如,$$$[5, 2, 3]$$$ 是 $$$[1, 5, 7, 8, 2, 4, 3]$$$ 的子序列。

可以证明,在给定的约束下,解总是存在。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例由一行组成,其中包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \le n$$$) - 上述参数。

保证所有测试用例的$$$n$$$总和不超过$$$10^7$$$。

输出

每个测试用例的第一行输出应包含一个整数 $$$m$$$ ($$$1 \le m \le 25$$$) - 您选择的序列的大小。

每个测试用例的第二行输出应包含 $$$m$$$ 整数 $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — 您选择的序列的元素。

如果有多个解决方案,请打印其中一个。

示例

输入 #1

5
2 2
6 1
8 8
9 3
10 7

输出 #1

1
1
5
2 3 4 5 6
7
1 1 1 1 1 1 1
4
7 1 4 1
4
1 2 8 3

注意

在第一个示例中,我们只需要一个加起来为 $$$1$$$ 的子序列,而不是加起来为 $$$2$$$ 的子序列。所以数组 $$$a=[1]$$$ 就足够了。

在第二个示例中,所有元素都大于 $$$k=1$$$,因此没有子序列加起来等于 $$$1$$$。 $$$1$$$ 和 $$$n$$$ 之间的所有其他整数都存在于数组中,因此有一个大小为 $$$1$$$ 的子序列与每个数字相加。