← 返回题目列表

Codeforces · 2031/C

C. Penchick 和烧烤面包

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

Penchick 喜欢两件事:方数和港式烧烤包!为了庆祝他的生日,Kohane 希望将它们与一份礼物结合起来:从左到右排列的 $$$n$$$ 烧烤面包。烧烤包的馅料有$$$10^6$$$可供选择,编号从$$$1$$$到$$$10^6$$$。为了确保 Penchick 会喜欢这份礼物,Kohane 有几个目标:

- 没有填充物仅使用一次;也就是说,每个填充物要么根本不出现,要么至少出现两次。
- 对于任何两个具有相同馅料的包子 $$$i$$$ 和 $$$j$$$,它们之间的距离 $$$|i-j|$$$ 必须是完全正方形$$$^{\text{*}}$$$。

帮助小羽找到一种有效的方法来选择包子的馅料,或者确定是否无法满足她的目标!如果有多个解决方案,请打印其中任何一个。

输入

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

每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) - 烧烤面包的数量。

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

输出

对于每个测试用例,如果不存在有效的填充选择,则输出 $$$-1$$$。否则,输出$$$n$$$个整数,其中第$$$i$$$个整数表示第$$$i$$$个烧烤包的馅料。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

2
3
12

输出 #1

-1
1 2 3 6 10 2 7 6 10 1 7 3

注意

在第一个测试用例中,不允许选择馅料“1 1 1”,因为包子 $$$1$$$ 和 $$$3$$$ 具有相同的馅料,但相距 $$$2$$$ 距离,这不是完美的正方形。也不允许选择填充物“1 1 2”,因为填充物 $$$2$$$ 仅使用一次。

在第二个测试用例中,该解决方案是有效的,因为没有馅料只使用一次,并且任何两个具有相同馅料的面包的间距等于完全平方数。例如,包子$$$1$$$和$$$10$$$的馅料都是$$$1$$$,间隔距离为$$$9=3^2$$$。同样,包子 $$$5$$$ 和 $$$9$$$ 都有馅料 $$$10$$$,间隔距离为 $$$4=2^2$$$。