迷宫中有 $$$n$$$ 个单元格,且单元格 $$$i$$$ ($$$1 \leq i \leq n$$$) 距出口 $$$n - i$$$ 公里。特别是,单元格 $$$n$$$ 是出口。另请注意,每个单元都连接到出口,但无法以任何方式从任何其他单元访问。
在每个牢房中,最初只有一个人被困在里面。您希望通过在每个单元格 $$$i$$$ ($$$1 \leq i \leq n$$$) 中安装一个传送器来帮助每个人尽可能接近出口,该传送器将该单元格中的人转移到另一个单元格 $$$a_i$$$。
迷宫主人当场抓住了你。她觉得好笑,让你继续,但有一些条件:
- 每个人都必须使用传送器恰好 $$$k$$$ 次。
- 任何单元格中的传送器都不能通往它所在的同一单元格。正式来说,$$$i \neq a_i$$$ 对于所有 $$$1 \leq i \leq n$$$。
你必须找到一种传送器配置,在使用传送器$$$k$$$次后,最小化所有个体距出口的距离总和,同时仍然满足迷宫所有者的限制。
如果有多种可能的配置,则可以输出其中任何一个。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) - 迷宫中的单元格数量和值 $$$k$$$。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数 - 传送器的目的地 $$$a_1, a_2, \ldots, a_n$$$ 按顺序,满足给定条件 ($$$1 \leq a_i \leq n$$$, $$$a_i \neq i$$$)。
示例
输入复制
22 13 2
输出复制
2 1 2 3 2
注意
第一个测试用例中,每个人的位置如下。
- 传送前:$$$[1, 2]$$$。
- 第一次传送:$$$[2, 1]$$$。
距离总和为 $$$(2-2) + (2-1) = 1$$$,这是可能的最小值。
在第二个测试用例中,每个人的位置如下。
- 传送前:$$$[1, 2, 3]$$$。
- 第一次传送:$$$[2, 3, 2]$$$。
- 第二次传送:$$$[3,2,3]$$$。
距离总和为 $$$(3-3) + (3-2) + (3-3) = 1$$$,这是可能的最小值。