分组

题目描述

给定一个长度为 $n$ 的整数数组 $a = \{a_1, a_2, \dots, a_n\}$ 和一个整数 $m$，其中 $m$ 是 $n$ 的一个因子。

你可以执行任意次下述操作：

• 选择两个下标 $i, j$ ($1 \le i, j \le n$)，如果它们满足 $i \pmod m = j \pmod m$，则可以交换 $a_i$ 和 $a_j$ 的值。

这个操作意味着，所有下标模 $m$ 同余的元素构成一个组，你可以在组内对元素进行任意的重新排列。

操作结束后，数组将被视为 $n/m$ 个连续的块，第 $r$ 个块（$1 \le r \le n/m$）包含元素 $\{a_{(r-1)\times m+1}, \dots, a_{r\times m}\}$。

你的目标是通过操作，最小化所有块的最大值之和，即最小化：

请输出一种能使该和最小化的最终数组排列。如果存在多种答案，输出字典序最小的一种。

输入格式

输入包含多组测试数据。

第一行输入一个整数 $T$，表示测试数据的组数。

对于每组测试数据： 第一行输入两个整数 $n, m$，满足 $m$ 整除 $n$。 第二行输入 $n$ 个整数 $a_1, a_2, \dots, a_n$。

输出格式

对于每组测试数据，输出一行，包含 $n$ 个用空格隔开的整数，表示你构造出的最优数组。

样例

样例输入

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

样例输出

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

提示

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le T \le 10^4$
• $1 \le m \le n \le 10^5$
• $m$ 是 $n$ 的因子。
• $1 \le a_i \le 10^9$
• 所有测试数据的 $n$ 之和不超过 $10^5$。