← 返回题目列表

Codeforces · 1927/E

E. 克莱弗排列

中文机器翻译题面 查看原题

给定两个整数 $$$n$$$ 和 $$$k$$$ ($$$k \le n$$$),其中 $$$k$$$ 是偶数。

长度 $$$n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 可以任意顺序。例如,$$$[2,3,1,5,4]$$$ 是一个排列,但 $$$[1,2,2]$$$ 不是排列(因为 $$$2$$$ 在数组中出现两次),并且 $$$[0,1,2]$$$ 也不是排列(因为 $$$n=3$$$,但 $$$3$$$ 不存在于数组中)。

你的任务是构造一个长度为 $$$n$$$ 的 $$$k$$$ 级排列。

如果在所有长度为 $$$k$$$ 的连续段的总和中(其中恰好有 $$$n - k + 1$$$),任何两个总和相差不超过 $$$1$$$,则排列称为 $$$k$$$ 级。

更正式地说,要确定排列 $$$p$$$ 是否为 $$$k$$$ 级,首先构造一个长度为 $$$n - k + 1$$$ 的数组 $$$s$$$,其中 $$$s_i=\sum_{j=i}^{i+k-1} p_j$$$,即第 $$$i$$$ 个元素等于总和$$$p_i, p_{i+1}, \dots, p_{i+k-1}$$$。

如果 $$$\max(s) - \min(s) \le 1$$$,则称为 $$$k$$$ 级排列。

找到长度为 $$$n$$$ 的任意 $$$k$$$ 级排列。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例的第一行也是唯一一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$,$$$k$$$ 是偶数),其中 $$$n$$$ 是所需排列的长度。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出长度为 $$$n$$$ 的任意 $$$k$$$ 级排列。

保证在给定约束的情况下这种排列始终存在。

示例

输入 #1

5
2 2
3 2
10 4
13 4
7 4

输出 #1

2 1
1 3 2
1 8 4 10 2 7 5 9 3 6
4 10 1 13 5 9 2 12 6 8 3 11 7
1 6 3 7 2 5 4

注意

在示例的第二个测试用例中:

- $$$p_1 + p_2 = 3 + 1 = 4$$$;
- $$$p_2 + p_3 = 1 + 2 = 3$$$。