巧克力和香草喜欢蛋糕。今天,一家蛋糕店的经理总共给了他们$$$2^{k+1}$$$蛋糕。蛋糕是均匀分配的,所以他们每个人最初都收到了 $$$2^k$$$ 蛋糕。
然而,Chocola 和 Vanilla 现在想要重新分配蛋糕,以便 Chocola 最终得到 $$$x$$$ 蛋糕,而 Vanilla 得到剩余的 $$$2^{k+1}-x$$$ 蛋糕。
在一个步骤中,他们可以执行以下两项操作之一:
- Chocola 把一半的蛋糕给了 Vanilla。仅当 Chocola 当前有偶数个蛋糕时才允许此操作。
- 香草把一半的蛋糕给了巧克力。仅当 Vanilla 当前有偶数个蛋糕时才允许此操作。
您的任务是确定达到目标分布所需的最少步骤数,并输出实现该最小值的任何有效操作序列。
可以证明,在给定的约束条件下,总是存在有效的解,并且所需的最小步骤数最多为$$$120$$$。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$k$$$ 和 $$$x$$$ ($$$1 \le k \le 60$$$, $$$1 \le x \le 2^{k+1}-1$$$) - 每个人最初收到 $$$2^k$$$ 蛋糕,$$$x$$$ 是 Chocola 之后应该拥有的蛋糕数量重新分配。
输出
对于每个测试用例,输出一个整数 $$$n$$$ ($$$0\le n\le 120$$$) 表示相应地重新分配蛋糕所需的最少步骤数。
在下一行,输出 $$$n$$$ 整数 $$$o_1, o_2, \ldots, o_n$$$ ($$$o_i = \mathtt{1}$$$ 或 $$$o_i = \mathtt{2}$$$),其中 $$$o_i = \mathtt{1}$$$ 表示$$$i$$$第步,Chocola 将一半的蛋糕给了 Vanilla(操作 1),$$$o_i = \mathtt{2}$$$ 表示 Vanilla 将一半的蛋糕给了 Chocola(操作 2)。
示例
输入复制
42 32 43 72 5
输出复制
2 2 1 0 3 2 2 1 2 1 2
注意
在第一个测试用例中,他们可以使用以下步骤,以便 Chocola 正好有 $$$x = 3$$$ 蛋糕,而 Vanilla 正好有 $$$2 ^ {k + 1} - x = 5$$$ 蛋糕。我们使用 $$$\{a, b\}$$$ 来表示 Chocola 目前有 $$$a$$$ 蛋糕,Vanilla 目前有 $$$b$$$ 蛋糕。
$$\{4, 4\} \xrightarrow{o_1 = \mathtt{2}} \{6, 2\} \xrightarrow{o_2 = \mathtt{1}} \{3, 5\}$$
在第二个测试用例中,Chocola 已经拥有恰好 $$$x = 4$$$ 蛋糕,而 Vanilla 已经拥有恰好 $$$2 ^ {k + 1} - x = 4$$$ 蛋糕,因此不需要任何操作。
在第三个测试用例中,他们可以使用以下步骤,以便 Chocola 正好有 $$$x = 7$$$ 蛋糕,而 Vanilla 正好有 $$$2 ^ {k + 1} - x = 9$$$ 蛋糕。
$$\{8, 8\} \xrightarrow{o_1 = \mathtt{2}} \{12, 4\} \xrightarrow{o_2 = \mathtt{2}} \{14, 2\} \xrightarrow{o_3 = \mathtt{1}} \{7, 9\}$$