310364: CF1822D. Super-Permutation

D. Super-Permutationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

A permutation is a sequence $n$ integers, where each integer from $1$ to $n$ appears exactly once. For example, $[1]$, $[3,5,2,1,4]$, $[1,3,2]$ are permutations, while $[2,3,2]$, $[4,3,1]$, $[0]$ are not.

Given a permutation $a$, we construct an array $b$, where $b_i = (a_1 + a_2 +~\dots~+ a_i) \bmod n$.

A permutation of numbers $[a_1, a_2, \dots, a_n]$ is called a super-permutation if $[b_1 + 1, b_2 + 1, \dots, b_n + 1]$ is also a permutation of length $n$.

Grisha became interested whether a super-permutation of length $n$ exists. Help him solve this non-trivial problem. Output any super-permutation of length $n$, if it exists. Otherwise, output $-1$.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the desired permutation.

The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output in a separate line:

• $n$ integers — a super-permutation of length $n$, if it exists.
• $-1$, otherwise.

If there are several suitable permutations, output any of them.

ExampleInput

4
1
2
3
6

Output

1
2 1
-1
6 5 2 3 4 1

题目大意：
一个排列是包含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 + ... + a_i) mod n。

如果序列[b_1 + 1, b_2 + 1, ..., b_n + 1]也是一个长度为n的排列，那么称序列[a_1, a_2, ..., a_n]为超排列。

Grisha对是否存在长度为n的超排列产生了兴趣。帮助他解决这个非平凡问题。如果存在长度为n的超排列，则输出该超排列。否则，输出-1。

输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例由一行组成，包含一个整数n（1≤n≤2*10^5）——所需排列的长度。
所有测试用例中n的总和不超过2*10^5。

输出数据格式：
对于每个测试用例，输出一行：
- 如果存在长度为n的超排列，则输出n个整数。
- 如果不存在，则输出-1。
如果有多个合适的排列，输出其中任意一个。题目大意： 一个排列是包含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 + ... + a_i) mod n。 如果序列[b_1 + 1, b_2 + 1, ..., b_n + 1]也是一个长度为n的排列，那么称序列[a_1, a_2, ..., a_n]为超排列。 Grisha对是否存在长度为n的超排列产生了兴趣。帮助他解决这个非平凡问题。如果存在长度为n的超排列，则输出该超排列。否则，输出-1。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例由一行组成，包含一个整数n（1≤n≤2*10^5）——所需排列的长度。 所有测试用例中n的总和不超过2*10^5。 输出数据格式： 对于每个测试用例，输出一行： - 如果存在长度为n的超排列，则输出n个整数。 - 如果不存在，则输出-1。 如果有多个合适的排列，输出其中任意一个。