关键观察

1. 下标的 $i \mod m$ 不会变化，所以每个模类是彼此独立的。

2. 数组被自然分成了 $n/m$ 个区块：

   • 第 $1$ 个区块：$a_1, a_2, \dots, a_m$
   • 第 $2$ 个区块：$a_{m+1}, \dots, a_{2m}$
   • 以此类推...

3. 在每个模类内部，我们可以自由交换元素的位置。

题目内容

给定一个长度为 $n$ 的数组 {$a_1,a_2,…,a_n$}，以及一个整数 $m$ ，保证 $m$ 是 $n$ 的因子 (即 $m|n$ )，你可以进行如下操作任意次：

• 选择两个不同的下标 $i,j$ ，满足 $i$ $mod$ $m=j$ $mod$ $m$ ，交换 $a_i$ 与 $a_j$ 。

请最小化如下目标函数：

$\sum^{n/m}_{r=1}max(a_{(r-1)m+1},a_{(r-1)m+2},...,a_{(r-1)m+m})$

井输出一种使该和值最小化后的数组。若存在多种最优方案，可以输出任意一种最优方案。

【名词解释】

• 取模：$x$ $mod$ $m$ 表示 $x$ 除以 $m$ 的余数。

输入描述

每个测试文件均包含多组测试数据。

第一行输入一个整数 $T(1≦T≦10^4)$ 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 $n,m(l≦n≦2×10^5;1≦m≦n;m|n)$ 。

第二行输入 $n$ 个整数 $a_1,a_2,…,a_n(1≦a_i≤10^9)$ 表示数组元素。

除此之外，保证单个测试文件的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行，输出 $n$ 个参数，表示在允许操作后、使目标函数取到最小值时的数组。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查答案正确性。

样例1

输入

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

说明

在第一组样例中：答案为

$max(a_1,a_2,a_3)+max(a_4,a_5,a_6)=max(2,1,5)+max(4,3,6)=5+6=11$ 。

可以证明此时答案最小。

样例2

输入

1
4 4
10 20 30 40

输出

10 20 30 40