Permutation Xority

 You are given an integer 

N$N$. Construct a permutation A$A$ of length N$N$ which is attractive.

A permutation is called attractive if the bitwise XOR of all absolute differences of adjacent pairs of elements is equal to 0$0$.

Formally, a permutation A=[A1,A2,…,AN]$A=[A_1,A_2,\dots ,A_N]$ of length N$N$ is said to be attractive if:

|A1−A2|⊕|A2−A3|⊕…⊕|AN−1−AN|=0$$|A_1-A_2|\oplus |A_2-A_3|\oplus \dots \oplus |A_{N-1}-A_N|=0$$

where ⊕$\oplus$ denotes the bitwise XOR operation.

Output any attractive permutation of length N$N$. If no attractive permutation exists, print −1$-1$ instead.

Note: A permutation of length N$N$ is an array A=[A1,A2,…,AN]$A=[A_1,A_2,\dots ,A_N]$ such that every integer from 1$1$ to N$N$ occurs exactly once in A$A$. For example, [1,2,3]$[1,2,3]$ and [2,3,1]$[2,3,1]$ are permutations of length 3$3$, but [1,2,1]$[1,2,1]$, [4,1,2]$[4,1,2]$, and [2,3,1,4]$[2,3,1,4]$ are not.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follows.
• Each test case consists of a single line of input, containing one integer N$N$.

Output Format

For each test case, output on a single line an attractive permutation of N$N$ integers, or −1$-1$ if no attractive permutation exists.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 2≤N≤105$2\le N\le {10}^5$
• Sum of N$N$ over all cases won't exceed 2⋅105$2\cdot {10}^5$.

Sample Input 1 

2
3
6

Sample Output 1 

3 2 1
5 2 3 6 4 1 

Explanation

Test Case 1$1$: |3−2|⊕|2−1|=1⊕1=0$|3-2|\oplus |2-1|=1\oplus 1=0$

Note that there are other correct answers — for example, [1,2,3]$[1,2,3]$ would also be accepted as correct.

Test Case 2$2$: |5−2|⊕|2−3|⊕|3−6|⊕|6−4|⊕|4−1|=3⊕1⊕3⊕2⊕3=0

• Tweet
• Share
• Share
• Share
• Share

Related Post