And Matching solution codeforces- You are given a set of nn (nn is always a power of 22) elements containing all integers 0,1,2,…,n−10,1,2,…,n−1 exactly once. Find n2n2 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 kk. Formally, if aiai and bibi are the elements of the ii-th pair, then the following must hold: ∑i=1n/2ai&bi=k,∑i=1n/2ai&bi=k, where && denotes the bitwise AND operation. If there are many solutions, print any of them, if there is no solution, print −1−1 instead.

And Matching solution codeforces

You are given a set of nn (nn is always a power of 22) elements containing all integers 0,1,2,,n10,1,2,…,n−1 exactly once.

Find n2n2 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 kk. Formally, if aiai and bibi are the elements of the ii-th pair, then the following must hold:
    i=1n/2ai&bi=k,∑i=1n/2ai&bi=k,

    where && denotes the bitwise AND operation.

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

Input And Matching solution codeforces

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

Each test case consists of a single line with two integers nn and kk (4n2164≤n≤216nn is a power of 220kn10≤k≤n−1).

The sum of nn over all test cases does not exceed 216216. All test cases in each individual input will be pairwise different.

Output And Matching solution codeforces

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

Otherwise, print n2n2 lines, the ii-th of them must contain aiai and bibi, the elements in the ii-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

Copy
4
4 0
4 1
4 2
4 3

output And Matching solution codeforces

Copy
0 3
1 2
0 2
1 3
0 1
2 3
-1
Note

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

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

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

In the fourth test, there is no solution.

Leave a Comment

Your email address will not be published.