← 返回题目列表

Codeforces · 1713/C

C. 构建排列

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

如果对于所有有效索引 $$$i$$$ ($$$0 \le i \le n-1$$$),$$$a_i + i$$$ 是一个完美的正方形 $$$^\dagger$$$,则大小为 $$$n$$$ 的 $$$\mathbf{0}$$$ 索引数组 $$$a$$$ 被称为良好。

给定一个整数$$$n$$$。找到 $$$[0,1,2,\ldots,n-1]$$$ 的一个好的排列$$$^\ddagger$$$ $$$p$$$ 或确定不存在这样的排列。

$$$^\dagger$$$ 如果存在一个整数 $$$y$$$ 使得 $$$x = y^2$$$,则整数 $$$x$$$ 被称为完全平方数。

$$$^\ddagger$$$ 数组 $$$b$$$ 是数组 $$$a$$$ 的排列,如果 $$$b$$$ 由 $$$a$$$ 的元素以任意顺序组成。例如,$$$[4,2,3,4]$$$ 是 $$$[3,2,4,4]$$$ 的排列,而 $$$[1,2,2]$$$ 不是 $$$[1,2,3]$$$ 的排列。

输入

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

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 排列 $$$p$$$ 的长度。

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

输出

对于每个测试用例,输出 $$$n$$$ 不同的整数 $$$p_0, p_1, \dots, p_{n-1}$$$ ($$$0 \le p_i \le n-1$$$) — 排列 $$$p$$$ — 如果答案存在,否则为 $$$-1$$$。

示例

输入 #1

3
3
4
7

输出 #1

1 0 2 
0 3 2 1 
1 0 2 6 5 4 3

注意

在第一个测试用例中,我们有 $$$n=3$$$。数组 $$$p = [1, 0, 2]$$$ 很好,因为 $$$1 + 0 = 1^2$$$、$$$0 + 1 = 1^2$$$ 和 $$$2 + 2 = 2^2$$$

在第二个测试用例中,我们有 $$$n=4$$$。数组 $$$p = [0, 3, 2, 1]$$$ 很好,因为 $$$0 + 0 = 0^2$$$、$$$3 + 1 = 2^2$$$、$$$2+2 = 2^2$$$ 和 $$$1+3 = 2^2$$$。