Adjacent Sum Greater than K

3.2

11 votes
, Greedy algorithm, Linear Search, Algorithms, Observation
Problem

A permutation of length N is an array of N integers such that every integer from 1 to N appears exactly once. For example, [2,3,5,4,1] is a permutation of length 5, while [1,2,2],[4,5,1,3] are not permutations.

You are given two integers N,K. Find a permutation P of length N such that Pi+Pi+1K for each 1i<N. If there are multiple permutations find the lexicographically smallest one. Print 1 if no such permutation exists.

A permutation P is lexicographically smaller than a permutation Q of the same length N if there exists an index 1iN such that P1=Q1,P2=Q2, and Pi<Qi.

Input format

  • The first line of input contains an integer T denoting the number of test cases. The description of each test case is as follows:
  • The first line of each test case contains two integers N,K.

Output format

For each test case, print 1 if no suitable permutation exists, otherwise print the lexicographically smallest permutation satisfying the conditions.

Constraints

1T1052N31051K2NSum of N over all test cases does not exceed 3105.

Sample Input
2
6 5
4 6
Sample Output
1 4 2 3 5 6 
-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  •  In the first test case, there are multiple permutations of length 6 which satisfy the given condition for K=5, for example[3,5,1,4,2,6],[1,5,2,3,4,6],[6,1,4,3,2,5]etc. [1,4,2,3,5,6] is the lexicographically smallest permutation among them.
  • In the second test case, there is no permutation of length 4 that satisfies the given condition for K=6. 

 

 

Editor Image

?