← 返回题目列表

Codeforces · 1822/D

D. 超级排列

中文机器翻译题面 查看原题

排列是 $$$n$$$ 整数序列,其中从 $$$1$$$ 到 $$$n$$$ 的每个整数只出现一次。例如,$$$[1]$$$、$$$[3,5,2,1,4]$$$、$$$[1,3,2]$$$ 是排列,而 $$$[2,3,2]$$$、$$$[4,3,1]$$$、$$$[0]$$$ 不是排列。

给定一个排列$$$a$$$,我们构造一个数组$$$b$$$,其中$$$b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n$$$。

如果 $$$[b_1 + 1, b_2 + 1, \dots, b_n + 1]$$$ 也是长度 $$$n$$$ 的排列,则数字 $$$[a_1, a_2, \dots, a_n]$$$ 的排列称为超排列。

Grisha 开始感兴趣是否存在长度 $$$n$$$ 的超级排列。帮助他解决这个不平凡的问题。输出长度为 $$$n$$$ 的任何超排列(如果存在)。否则,输出$$$-1$$$。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例由一行组成,其中包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 所需排列的长度。

所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,在单独的行中输出:

- $$$n$$$ 整数 — 长度为 $$$n$$$ 的超排列(如果存在)。
- $$$-1$$$,否则。

如果有多个合适的排列,则输出其中任何一个。

示例

输入 #1

4
1
2
3
6

输出 #1

1
2 1
-1
6 5 2 3 4 1