1722G.md (1246B)
1 Source: https://codeforces.com/problemset/problem/1722/G 2 3 G. Even-Odd XOR 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Given an integer $n$, find any array $a$ of $n$ distinct nonnegative integers less than $2^{31}$ such that the [bitwise XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of the elements on odd indices equals the bitwise XOR of the elements on even indices. 22 23 Input 24 25 The first line of the input contains an integer $t$ ($1 \leq t \leq 629$) — the number of test cases. 26 27 Then $t$ lines follow, each containing a single integer $n$ $(3 \leq n \leq 2\cdot10^5)$ — the length of the array. 28 29 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 30 31 Output 32 33 For each test case, output one line containing $n$ distinct integers that satisfy the conditions. 34 35 If there are multiple answers, you can output any of them. 36 37 Example 38 39 Input 40 41 ``` 42 7 43 8 44 3 45 4 46 5 47 6 48 7 49 9 50 ``` 51 52 Output 53 54 ``` 55 4 2 1 5 0 6 7 3 56 2 1 3 57 2 1 3 0 58 2 0 4 5 3 59 4 1 2 12 3 8 60 1 2 3 4 5 6 7 61 8 2 3 7 4 0 5 6 9 62 ``` 63 64 Note 65 66 In the first test case the XOR on odd indices is $4 \oplus 1 \oplus 0 \oplus 7 = 2$ and the XOR on even indices is $2 \oplus 5 \oplus 6 \oplus 3= 2$.