题目内容

给定一个长度为 $n$ 的整数序列 $x_1, x_2, \dots, x_n$ 和一个正步长 $d$。 你可以进行任意次如下操作： 选择一个下标 $i$（$1 \le i \le n-d$），交换 $x_i$ 与 $x_{i+d}$ 的值。

在可以无限次操作的前提下，你需要给出最终能够得到的字典序最大的序列。

【字典序比较规则】从两个序列的第一个元素开始逐个比较，直到找到第一个不同的元素，该元素较大的序列字典序较大。

数据约束：

• 单个测试文件中测试数据的组数 $T$ 满足 $1 \le T \le 2 \times 10^5$。
• 每组数据的序列长度 $n$ 满足 $1 \le n \le 2 \times 10^5$，步长 $d$ 满足 $1 \le d \le n$。
• 序列中的每个整数绝对值不超过 $10^9$。
• 所有测试数据的 $n$ 之和不超过 $5 \times 10^5$。

输入描述

第一行包含一个整数 $T$，表示测试数据组数。 接下来每组数据按以下格式给出：

• 第一行包含两个整数 $n$ 和 $d$，分别表示序列长度和步长。
• 第二行包含 $n$ 个整数，表示初始序列 $x_1, x_2, \dots, x_n$。

输出描述

对于每组测试数据，输出一行 $n$ 个整数，表示经过若干次交换后能够得到的字典序最大的序列，相邻数字之间用空格分隔。

样例1

输入

1
4 2
1 2 3 4

输出

3 4 1 2

说明

给定 $n=4, d=2$，序列为 $[1,2,3,4]$。 按照下标模 $d$ 分组：

• 模 $0$ 组（对应位置 1 和 3）：元素为 1 和 3，降序排列为 [3, 1]。
• 模 $1$ 组（对应位置 2 和 4）：元素为 2 和 4，降序排列为 [4, 2]。 按原位置顺序回填，最终得到序列 [3, 4, 1, 2]，这是字典序最大的序列。

样例2

输入

3
3 3
5 2 8
5 3
-1 3 0 2 -4
6 2
10 20 30 40 50 60

输出

5 2 8
2 3 0 -1 -4
50 60 30 40 10 20

说明

输入包含三组数据。 第一组：$n=3, d=3$，每个下标模 $3$ 各成一组，每组只有一个元素，无法进行任何交换，序列保持 5 2 8。 第二组：$n=5, d=3$。分组：

• 模 $0$ 组（位置 1, 4）：元素 -1, 2，降序为 [2, -1]；
• 模 $1$ 组（位置 2, 5）：元素 3, -4，降序为 [3, -4]；
• 模 $2$ 组（位置 3）：元素 0。 回填得到 [2, 3, 0, -1, -4]。 第三组：$n=6, d=2$。分组：
• 模 $0$ 组（位置 1, 3, 5）：元素 10, 30, 50，降序为 [50, 30, 10]；
• 模 $1$ 组（位置 2, 4, 6）：元素 20, 40, 60，降序为 [60, 40, 20]。 回填得到 [50, 60, 30, 40, 10, 20]。

样例3

输入

2
5 1
3 1 4 1 5
4 2
7 -2 7 -2

输出

5 4 3 1 1
7 -2 7 -2

说明

第一组：$d=1$，所有位置属于同一组，可以任意排列。降序排序后得到 [5, 4, 3, 1, 1]，即为字典序最大的序列。 第二组：$n=4, d=2$。分组：

• 模 $0$ 组（位置 1, 3）：元素 7, 7，降序仍为 [7, 7]；
• 模 $1$ 组（位置 2, 4）：元素 -2, -2，降序为 [-2, -2]。 回填得到 [7, -2, 7, -2]。每个位置只能从其所在组取最大剩余元素，因此该序列即为字典序最大的结果。