← 返回题目列表

Codeforces · 1934/D1

D1. XOR 中断 --- 独奏版本

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

这是问题的单独版本。请注意,此问题的解决方案可能会或可能不会与游戏版本的解决方案共享想法。您可以独立解决两个版本并获得分数。

只有当两个版本的问题都得到解决后,你才可以进行黑客攻击。

给定一个整数变量 $$$x$$$,初始值为 $$$n$$$。单次中断操作由以下步骤组成:

- 选择一个值 $$$y$$$,使得 $$$0 \lt y \lt x$$$ 和 $$$0 \lt (x \oplus y) \lt x$$$。
- 通过设置 $$$x = y$$$ 或设置 $$$x = x \oplus y$$$ 来更新 $$$x$$$。

您不需要最小化操作次数。

这里$$$\oplus$$$表示按位异或运算。

输入

第一行包含一个正整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq m \lt n \leq 10^{18}$$$) - $$$x$$$ 的初始值和 $$$x$$$ 的目标值。

输出

对于每个测试用例,按以下格式输出答案。

如果在 $$$63$$$ 操作中不可能达到 $$$m$$$,则打印 $$$-1$$$。

否则,

第一行应包含 $$$k$$$ ($$$1 \leq k \leq 63$$$) — 其中 $$$k$$$ 是所需的操作数。

下一行应包含 $$$k+1$$$ 整数 - 每个中断操作后变量 $$$x$$$ 发生变化的序列。 $$$1$$$-st 和 $$$k+1$$$-th 整数应分别为 $$$n$$$ 和 $$$m$$$。

示例

输入 #1

3
7 3
4 2
481885160128643072 45035996273704960

输出 #1

1
7 3
-1
3
481885160128643072 337769972052787200 49539595901075456 45035996273704960

注意

在第一个测试用例$$$n = 7$$$中,对于第一个操作$$$x = 7$$$,如果我们选择$$$y = 3$$$,则$$$(7 \oplus 3) \lt 7$$$,因此我们可以用$$$3$$$更新$$$x$$$,它等于$$$m$$$。

在第二个测试用例 $$$n = 4$$$ 中,对于第一个操作 $$$x = 4$$$。

如果我们选择:

- $$$y = 1$$$ 然后 $$$(4 \oplus 1) \gt 4$$$
- $$$y = 2$$$ 然后 $$$(4 \oplus 2) \gt 4$$$
- $$$y = 3$$$ 然后 $$$(4 \oplus 3) \gt 4$$$

因此我们无法进行第一个操作,也不可能使$$$x = 2$$$。