题目描述

给定一个包含 $n$ 个元素的集合（$n$ 总是 $2$ 的幂），该集合恰好包含所有整数 $0, 1, 2, \ldots, n-1$。

请将这些元素分成 $\frac{n}{2}$ 对，使得：

• 集合中的每个元素恰好属于一对。
• 所有对中元素按位与的和恰好等于 $k$。形式化地说，若第 $i$ 对为 $a_i$ 和 $b_i$，则需满足：$$\sum_{i=1}^{n/2}{a_i & b_i} = k$$，其中 $\,\&\,$ 表示按位与运算。

如果有多种方案，输出任意一种。如果无解，则输出 $-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}$ 行，每行两个整数 $a_i$ 和 $b_i$，表示一对元素。

如果有多种方案，输出任意一种。对的顺序和对内元素顺序均不限。

说明/提示

在第一个测试样例中，$(0\&3)+(1\&2)=0$。

在第二个测试样例中，$(0\&2)+(1\&3)=1$。

在第三个测试样例中，$(0\&1)+(2\&3)=2$。

在第四个测试样例中，无解。

由 ChatGPT 4.1 翻译

样例

4
4 0
4 1
4 2
4 3

0 3
1 2
0 2
1 3
0 1
2 3
-1