311054: CF1927E. Klever Permutation

E. Klever Permutationtime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given two integers $n$ and $k$ ($k \le n$), where $k$ is even.

A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in any order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation (as $2$ appears twice in the array) and $[0,1,2]$ is also not a permutation (as $n=3$, but $3$ is not present in the array).

Your task is to construct a $k$-level permutation of length $n$.

A permutation is called $k$-level if, among all the sums of continuous segments of length $k$ (of which there are exactly $n - k + 1$), any two sums differ by no more than $1$.

More formally, to determine if the permutation $p$ is $k$-level, first construct an array $s$ of length $n - k + 1$, where $s_i=\sum_{j=i}^{i+k-1} p_j$, i.e., the $i$-th element is equal to the sum of $p_i, p_{i+1}, \dots, p_{i+k-1}$.

A permutation is called $k$-level if $\max(s) - \min(s) \le 1$.

Find any $k$-level permutation of length $n$.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. This is followed by the description of the test cases.

The first and only line of each test case contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$, $k$ is even), where $n$ is the length of the desired permutation.

It is guaranteed that the sum of $n$ for all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output any $k$-level permutation of length $n$.

It is guaranteed that such a permutation always exists given the constraints.

ExampleInput

5
2 2
3 2
10 4
13 4
7 4

Output

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

Note

In the second test case of the example:

• $p_1 + p_2 = 3 + 1 = 4$;
• $p_2 + p_3 = 1 + 2 = 3$.

The maximum among the sums is $4$, and the minimum is $3$.

题目大意：
这个题目要求构造一个长度为 n 的 k-level 排列。给定两个整数 n 和 k (k ≤ n)，其中 k 是偶数。一个排列是 n 个从 1 到 n 的不同整数的任意排列。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列（因为 2 在数组中出现了两次），[0,1,2] 也不是一个排列（因为 n=3，但 3 不在数组中）。任务是要构造一个长度为 n 的 k-level 排列。

一个排列被称为 k-level，如果所有长度为 k 的连续段的和（共有 n - k + 1 个）之间任何两个和的差不超过 1。更正式地，要确定排列 p 是否为 k-level，首先构造一个长度为 n - k + 1 的数组 s，其中 s_i = Σ_{j=i}^{i+k-1} p_j，即第 i 个元素等于 p_i, p_{i+1}, …, p_{i+k-1} 的和。一个排列被称为 k-level，如果 max(s) - min(s) ≤ 1。找到任意一个 k-level 排列。

输入输出数据格式：
输入：
第一行包含一个整数 t (1 ≤ t ≤ 10^4) — 测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 k (2 ≤ k ≤ n ≤ 2 * 10^5, k 是偶数)，其中 n 是所需排列的长度。
保证所有测试用例的 n 之和不超过 2 * 10^5。

输出：
对于每个测试用例，输出任意一个 k-level 排列的长度为 n。
保证在给定的约束下总是存在这样的排列。

示例输入输出：
输入：
```
5
2 2
3 2
10 4
13 4
7 4
```
输出：
```
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
```题目大意： 这个题目要求构造一个长度为 n 的 k-level 排列。给定两个整数 n 和 k (k ≤ n)，其中 k 是偶数。一个排列是 n 个从 1 到 n 的不同整数的任意排列。例如，[2,3,1,5,4] 是一个排列，但 [1,2,2] 不是一个排列（因为 2 在数组中出现了两次），[0,1,2] 也不是一个排列（因为 n=3，但 3 不在数组中）。任务是要构造一个长度为 n 的 k-level 排列。 一个排列被称为 k-level，如果所有长度为 k 的连续段的和（共有 n - k + 1 个）之间任何两个和的差不超过 1。更正式地，要确定排列 p 是否为 k-level，首先构造一个长度为 n - k + 1 的数组 s，其中 s_i = Σ_{j=i}^{i+k-1} p_j，即第 i 个元素等于 p_i, p_{i+1}, …, p_{i+k-1} 的和。一个排列被称为 k-level，如果 max(s) - min(s) ≤ 1。找到任意一个 k-level 排列。 输入输出数据格式： 输入： 第一行包含一个整数 t (1 ≤ t ≤ 10^4) — 测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含两个整数 n 和 k (2 ≤ k ≤ n ≤ 2 * 10^5, k 是偶数)，其中 n 是所需排列的长度。 保证所有测试用例的 n 之和不超过 2 * 10^5。 输出： 对于每个测试用例，输出任意一个 k-level 排列的长度为 n。 保证在给定的约束下总是存在这样的排列。 示例输入输出： 输入： ``` 5 2 2 3 2 10 4 13 4 7 4 ``` 输出： ``` 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 ```