Formally, if the permutations are A and B, then, the value A_i \& B_i must be constant over all 1\le i \le N.
Help Chef by providing him 2 such permutations. If it is not possible to construct such permutations, print -1 instead.
In case N = 1, A =  and B = .
Now let’s discuss for N \geq 2.
Observation 1: The only constant value possible is 0.
Any number greater than 1, say c would not be possible since then no number can be paired with 1 to give their AND as c. If we select the constant as 1, then also no number can be paired 2 to get their AND as 1. Thus by elimination of choice, only 0 is a viable candidate.
Observation 2: It is not possible if N is odd(and greater than 1).
Say for N = 2k + 1. There would be k+1 odd numbers and k even numbers. Since each odd number has their first bit set and to unset it we would need an even number but since the number of odd numbers is more than that of even numbers, therefore it won’t be possible to make such pairs.
Observation 3: if there are two numbers say, a and b, then if
sum of a and b is of the form 2^x - 1, then their AND is 0.
Thus when N is even, we can find all such possible pairs by going from N to 1, and for each number i(not already included in a pair), we can find its pair k by subtracting i from p where p is formed by setting all unset bits(right of MSB) of i.
This way after finding all the pairs, we can construct our two permutations.
O(N), for each test case.