CF1630A.And Matching

You are given a set of $n$ ($n$ is always a power of $2$) elements containing all integers $0, 1, 2, \ldots, n-1$ exactly once.

Find $\frac{n}{2}$ pairs of elements such that:

• Each element in the set is in exactly one pair.
• The sum over all pairs of the bitwise AND of its elements must be exactly equal to $k$. Formally, if $a_i$ and $b_i$ are the elements of the $i$-th pair, then the following must hold: $$\sum_{i=1}^{n/2}{a_i \& b_i} = k,$$ where $\&$ denotes the bitwise AND operation.

If there are many solutions, print any of them, if there is no solution, print $-1$ instead.

给你一个包含 $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$。

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 400$) — the number of test cases. Description of the test cases follows.

Each test case consists of a single line with two integers $n$ and $k$ ($4 \leq n \leq 2^{16}$, $n$ is a power of $2$, $0 \leq k \leq n-1$).

The sum of $n$ over all test cases does not exceed $2^{16}$. All test cases in each individual input will be pairwise different.

输入包含多个测试用例。第一行包含一个整数 $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}$。每个单独输入中的所有测试用例两两不同。

For each test case, if there is no solution, print a single line with the integer $-1$.

Otherwise, print $\frac{n}{2}$ lines, the $i$-th of them must contain $a_i$ and $b_i$, the elements in the $i$-th pair.

If there are many solutions, print any of them. Print the pairs and the elements in the pairs in any order.

对于每个测试用例，若无解，则输出一行整数 $-1$。

否则，输出 $\frac{n}{2}$ 行，其中第 $i$ 行必须包含第 $i$ 个数对中的两个元素 $a_i$ 和 $b_i$。

若存在多个解，输出任意一个即可。数对之间以及每个数对内的元素顺序均不限。

In the first test, $(0\&3)+(1\&2) = 0$.

In the second test, $(0\&2)+(1\&3) = 1$.

In the third test, $(0\&1)+(2\&3) = 2$.

In the fourth test, there is no solution.

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

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

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

在第四个测试中，无解。