#CF2048B. 凯文与排列

凯文与排列

B. Kevin 与排列

时间限制:每个测试用例 1 秒 内存限制:每个测试用例 256 MB

Kevin 是排列问题的高手。你正和 Kevin 在黑森林散步,闲暇时,他想向你提出如下问题。

给定两个正整数 nnkk,构造一个长度为 nn 的排列 p^*p,使得所有长度为 kk 的子数组 ^\dagger 的最小值之和尽可能小。 形式化地说,你需要最小化:

$$\sum_{i=1}^{n-k+1}\left(\min_{j=i}^{i+k-1} p_j\right) $$

^* 长度为 nn 的排列是一个由 11nnnn 个不同整数按任意顺序组成的数组。 例如 [2,3,1,5,4][2,3,1,5,4] 是一个排列,但 [1,2,2][1,2,2] 不是(数字 22 出现了两次),[1,3,4][1,3,4] 也不是(n=3n=3 但数组中出现了 44)。

^\dagger 数组 aa 是数组 bb 的一个子数组,如果 aa 可以通过从 bb 的开头删除若干(可以是 00 个或全部)元素、并从末尾删除若干(可以是 00 个或全部)元素得到。 如果删除元素的位置集合不同,则认为是不同的子数组。


输入格式

每个测试包含多组数据。 第一行一个整数 tt1t1031\le t\le 10^3),表示测试用例数量。

每组测试用例一行,包含两个整数 nnkk1kn1051\le k\le n\le 10^5)。

保证所有测试用例的 nn 之和不超过 10510^5

输出格式

对于每组测试用例,在一行输出 nn 个整数 —— 即你构造的排列 pp

如果有多种合法答案,输出任意一种即可。


样例输入

3
4 2
6 1
8 3

样例输出

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

样例说明

在第一个测试用例中,k=2k=2,考虑所有长度为 22 的子数组: 子数组 [p1,p2][p_1,p_2] 的最小值为 11, 子数组 [p2,p3][p_2,p_3] 的最小值为 11, 子数组 [p3,p4][p_3,p_4] 的最小值为 22。 总和 1+1+2=41+1+2=4 是所有排列中最小的。

在第二个测试用例中,所有长度为 11 的子数组的最小值依次为 5,2,1,6,4,35,2,1,6,4,3,其和 5+2+1+6+4+3=215+2+1+6+4+3=21 可以证明是最小的。