CF1927E.Klever Permutation

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

You are given two integers nn and kk ( knk \le n ), where kk is even.

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

Your task is to construct a kk -level permutation of length nn .

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

More formally, to determine if the permutation pp is kk -level, first construct an array ss of length nk+1n - k + 1 , where si=j=ii+k1pjs_i=\sum_{j=i}^{i+k-1} p_j , i.e., the ii -th element is equal to the sum of pi,pi+1,,pi+k1p_i, p_{i+1}, \dots, p_{i+k-1} .

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

Find any kk -level permutation of length nn .

输入格式

The first line of the input contains a single integer tt ( 1t1041 \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 nn and kk ( 2kn21052 \le k \le n \le 2 \cdot 10^5 , kk is even), where nn is the length of the desired permutation.

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

输出格式

For each test case, output any kk -level permutation of length nn .

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

输入输出样例

  • 输入#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

说明/提示

In the second test case of the example:

  • p1+p2=3+1=4p_1 + p_2 = 3 + 1 = 4 ;
  • p2+p3=1+2=3p_2 + p_3 = 1 + 2 = 3 .

The maximum among the sums is 44 , and the minimum is 33 .

首页