409179: GYM103449 G Xor Plains

After getting money from the bank, Glob and Madf started their adventure. They have come across the Xor Plains, right below the Frozen Mountains.

The Plains can be represented as an array of $$$n$$$ distinct integers, where each element represents the height of the plains in that area. Let this array be called the 'plains array'. Glob knows that the bitwise xor of all heights is equal to $$$0$$$ and that the plains array is lexicographically minimal among all arrays whose xor-sum is $$$0$$$.

Glob has asked Madf to find the plains array, since he is too busy being the hero and gazing into the sunset. Madf succeeded, but can you?

The first line of input contains one integer $$$k$$$ ($$$1 \le k \lt 1500$$$), the number of testcases. The second line of input contains $$$k$$$ space separated integers $$$n_i$$$ ($$$3 \le n_i \le 2 \cdot 10^5$$$), the sizes of the plains arrays. It is guaranteed that the sum of $$$n$$$ across all testcases does not exceed $$$10^6$$$ (i.e. $$$\sum{n} \le 10^6$$$).

For each testcase, print $$$n_i$$$ distinct numbers from the interval $$$[1,10^6]$$$, representing the plains arrays.

• Subtask 1 (10 points): $$$n_i+1$$$ is a power of $$$2$$$;
• Subtask 2 (20 points): $$$n_i, \Sigma n \le 300$$$;
• Subtask 3 (30 points): $$$n_i, \Sigma n \le 3000$$$;
• Subtask 4 (40 points): No further constraints.

3
3 5 6

1 2 3
1 2 4 8 15
1 2 3 4 8 12

These are the lexicographically minimal arrays whose xorsum is 0.

• $$$1 \wedge 2 \wedge 3=0$$$
• $$$1 \wedge 2 \wedge 4 \wedge 8 \wedge 15=0$$$
• $$$1 \wedge 2 \wedge 3 \wedge 4 \wedge 8 \wedge 12=0$$$