当前没有测试数据。

C2. XOR-convenience (困难版)

题目描述

本题为该问题的困难版本，与简易版本的区别在于本题要求满足条件的下标范围为 $1 \le i \le n-1$。请注意，困难版本的正确解法不一定适用于简易版本。

给定一个正整数 $n$，请你构造一个长度为 $n$ 的排列 $p$，使得对于每一个满足 $1 \le i \le n-1$ 的下标 $i$，都存在一个下标 $j$（$i \le j \le n$），满足 $p_i = p_j \oplus i$；若不存在这样的排列，则输出 $-1$。

注1：长度为 $n$ 的排列指的是由 $1$ 到 $n$ 的所有整数组成的、每个数恰好出现一次的数组。例如，$[2,3,1,5,4]$ 是一个合法排列，而 $[1,2,2]$（数字 $2$ 重复）和 $[1,3,4]$（$n=3$ 但出现数字 $4$）均不是合法排列。 注2：$\oplus$ 表示按位异或运算。

输入输出格式

输入格式

输入包含多组测试用例。 第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 接下来 $t$ 行，每行输入一个整数 $n$（$3 \le n \le 2 \times 10^5$），表示排列的长度。

保证所有测试用例的 $n$ 之和不超过 $2 \times 10^5$。

输出格式

对于每组测试用例：

• 若存在合法排列，输出一行 $n$ 个整数，表示该排列 $p$；
• 若不存在合法排列，输出一行 $-1$。

若存在多个合法解，输出任意一个即可。

样例

样例输入

2
3
4

样例输出

2 1 3
-1

备注

• 第一个测试用例中，排列 $p=[2,1,3]$ 满足条件：$p_2=1$，且 $p_3 \oplus 2 = 3 \oplus 2 = 1$（对应 $i=2$）；同时对于 $i=1$，可验证 $p_1=2$，存在 $j=3$ 使得 $p_3 \oplus 1 = 3 \oplus 1 = 2$，因此合法。
• 第二个测试用例中，不存在满足条件的排列，故输出 $-1$。

数据范围

• $1 \le t \le 10^4$
• $3 \le n \le 2 \times 10^5$
• 所有测试用例的 $n$ 之和 $\le 2 \times 10^5$

时空限制

• 时间限制：2 秒/测试点
• 内存限制：256 MB/测试点