A11340. Klever Permutation

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$ .

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$ .

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

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

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$ .