给你一组 $$$n$$$ ($$$n$$$ 始终是 $$$2$$$ 的幂)元素,其中包含所有整数 $$$0, 1, 2, \ldots, n-1$$$ 恰好一次。
查找 $$$\frac{n}{2}$$$ 元素对,使得:
- 集合中的每个元素恰好是一对。
- 其元素的所有按位 AND 对的总和必须完全等于 $$$k$$$。形式上,如果 $$$a_i$$$ 和 $$$b_i$$$ 是第 $$$i$$$ 对的元素,则必须满足以下条件: $$$$$$\sum_{i=1}^{n/2}{a_i \& b_i} = k,$$$$$$ 其中 $$$\&$$$ 表示按位 AND 运算。
如果有很多解,则打印其中任意一个,如果没有解,则打印$$$-1$$$。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 400$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例由一行包含两个整数 $$$n$$$ 和 $$$k$$$ 组成($$$4 \leq n \leq 2^{16}$$$,$$$n$$$ 是 $$$2$$$ 的幂,$$$0 \leq k \leq n-1$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$2^{16}$$$。每个单独输入中的所有测试用例都将成对不同。
输出
对于每个测试用例,如果没有解决方案,则打印带有整数 $$$-1$$$ 的单行。
否则,打印 $$$\frac{n}{2}$$$ 行,其中第 $$$i$$$ 行必须包含 $$$a_i$$$ 和 $$$b_i$$$,即第 $$$i$$$ 对中的元素。
如果有很多解决方案,请打印其中任何一个。以任意顺序打印对和对中的元素。
示例
输入 #1
4 4 0 4 1 4 2 4 3
输出 #1
0 3 1 2 0 2 1 3 0 1 2 3 -1
注意
在第一个测试中,$$$(0\&3)+(1\&2) = 0$$$。
在第二个测试中,$$$(0\&2)+(1\&3) = 1$$$。
在第三个测试中,$$$(0\&1)+(2\&3) = 2$$$。
第四次测试,无解。