解题思路

一次操作可以交换 $a_i$ 和 $a_{i+k}$，所以一个位置上的数只能在和它下标同余的那一组里移动。

也就是说，数组会被分成若干组：

• 第 $1, 1+k, 1+2k, \dots$ 个位置是一组
• 第 $2, 2+k, 2+2k, \dots$ 个位置是一组
• $\dots$

题目内容

给定一个长度为 $n$ 的整数数组 $a$ 和一个正整数 $k$。你可以进行任意次如下操作：

• 选择一个下标 $i$，满足 $1 \le i$ 且 $i+k \le n$，将 $a_i$与$a_{i+k}$ 交换（即把位置相差 $k$ 的两个元素对调）。

在可以无限次操作的前提下，请你给出最终能得到的字典序最大的数组。

【字典顺序比较】从两个数组的第一个元素开始逐个比较，直到找到第一个不同的元素，较大元素所在的数组的字典序较大。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 \le T \le 2 \times 10^5)$ 代表数据组数，每组测试数据描述如下：

• 第一行输入两个整数 $n,k$（$1 \le n \le 2 \times 10^5$，$1 \le k \le n$）；

• 第二行输入 $n$ 个整数 $a_1,a_2,\dots,a_n$（$-10^9 \le a_i \le 10^9$）。

保证所有测试中 $n$ 的总和不超过 $5 \times 10^5$。

输出描述

对于每组测试数据，输出一行 $n$ 个整数，表示在上述操作下可获得的字典序最大的数组。

样例1

输入

3
5 2
3 1 4 1 5
6 3
1 6 2 5 3 4
4 1
9 8 7 6

输出

5 1 4 1 3
5 6 4 1 3 2
9 8 7 6