And Matching solution codeforces
-
For Solution
Click Here!
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.
The input consists of multiple test cases. The first line contains a single integer tt (1≤t≤4001≤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 (4≤n≤2164≤n≤216, nn is a power of 22, 0≤k≤n−10≤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.
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.
input
4 4 0 4 1 4 2 4 3
output And Matching solution codeforces
0 3 1 2 0 2 1 3 0 1 2 3 -1
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.
-
For Solution
Click Here!