← 返回题目列表

Codeforces · 1630/A

A. 和匹配

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

给你一组 $$$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$$$。

第四次测试,无解。