No tag edit access

The problem statement has recently been changed. View the changes.

×
A. And Matching

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Input

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.

Output

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.

Example

Input

4 4 0 4 1 4 2 4 3

Output

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

Note

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.

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/31/2023 00:30:30 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|