← 返回题目列表

Codeforces · 2071/B

B. 完美

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

长度为 $$$n$$$$$$^{\text{∗}}$$$ 的排列 $$$p$$$ 为 完美 如果对于每个索引 $$$i$$$ ($$$1 \le i \le n$$$),它满足以下条件:

  • 前 $$$i$$$ 元素 $$$p_1 + p_2 + \ldots + p_i$$$ 的总和为 不 一个完美的正方形$$$^{\text{†}}$$$。

你希望事情变得完美。给定一个正整数$$$n$$$,找到一个 完美 长度 $$$n$$$ 的排列,或者如果不存在则打印 $$$-1$$$。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

$$$^{\text{†}}$$$完全平方数是整数的平方,例如,$$$9=3^2$$$ 是完全平方数,但 $$$8$$$ 和 $$$14$$$ 不是完全平方数。

输入

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

每个测试用例的第一行也是唯一一行包含一个整数 $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^6$$$。

输出

对于每个测试用例:

  • 如果不存在解,则打印单个整数 $$$-1$$$。
  • 否则,打印 $$$n$$$ 整数 $$$p_1,p_2,\ldots,p_n$$$ — 您找到的 完美 排列。

如果有多个解决方案,请打印其中任何一个。

示例

输入
复制

3
1
4
5

输出
复制

-1
2 4 1 3
5 1 4 3 2

注意

在第一个测试用例中,只有一个长度 $$$n = 1$$$ 的排列,即 $$$p = [1]$$$,这不是 完美:

  • $$$p_1 = 1 = x^2$$$ 对于 $$$x = 1$$$。

在第二个测试用例中,一种可能的情况是 完美 长度 $$$n = 4$$$ 的排列为 $$$p = [2, 4, 1, 3]$$$:

  • $$$p_1 = 2 \neq x^2$$$;
  • $$$p_1 + p_2 = 2 + 4 = 6 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 = 2 + 4 + 1 = 7 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 + p_4 = 2 + 4 + 1 + 3 = 10 \neq x^2$$$。

在第三个测试用例中,一种可能的情况是 完美 长度 $$$n = 5$$$ 的排列为 $$$p = [5, 1, 4, 3, 2]$$$:

  • $$$p_1 = 5 \neq x^2$$$;
  • $$$p_1 + p_2 = 5 + 1 = 6 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 = 5 + 1 + 4 = 10 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 + p_4 = 5 + 1 + 4 + 3 = 13 \neq x^2$$$;
  • $$$p_1 + p_2 + p_3 + p_4 + p_5 = 5 + 1 + 4 + 3 + 2 = 15 \neq x^2$$$。