Kalakeya

All submissions for this problem are available.
The Kalakeyas were a powerful, ferocious and cruel clan of Danavas. They were known to be really strong and they did not have any war strategy. They would just attack the enemy randomly and overpower them with sheer number of soldiers. However, we all know that Baahubali and Bhallaladeva defeated the Kalakeyas by following the Thrishul strategy, and successfully defended their kingdom Maahishmati. We also know that Baahubali was very smart, and the truth is that he predicted how the Kalakeyas would attack and devised a counter strategy for the same, the night before the war. This is what he found:
The Kalakeyas had N forts, numbered 1 to N and Baahubali had N soldiers, numbered 1 to N. Baahubali discovered that he can permute his soldiers in any way to get a permutation of 1 to N => P_{1}, P_{2}, ..., P_{N}. He would then send his soldiers to attack the forts in the following way: soldier P_{1} attacks fort 1, soldier P_{2} attacks fort 2, ..., soldier P_{N} attacks fort N. It is easy to note that each soldier attacks exactly one fort and no two soldiers attack the same fort. Baahubali also got to know about a secret key of the Kalakeyas, which is an integer K. A soldier X can destroy a fort Y, iff abs(X  Y) >= K. For more details on the abs() function, check here.
Your task is to determine whether Baahubali's soldiers can be permuted in some way, such that all forts can be destroyed. In other words, for a permutation P_{1}, P_{2}, ..., P_{N}, Baahubali's soldiers can destroy all the forts iff abs(P_{i}  i) >= K, for all 1 <= i <= N. If this is possible, you are also required to output the lexicographically smallest such permutation. If it is not possible, output 1.
Note: A permutation A_{1}, A_{2}, ..., A_{N} is said to be lexicographically smaller than a permutation B_{1}, B_{2}, ..., B_{N}, if and only if at the first i where A_{i} and B_{i} differ, A_{i} comes before B_{i}. You can refer here for a more detailed definition of lexicographic ordering.
Input
The first line of input consists of a single integer T denoting the number of test cases. Each of the following T lines contain two space separated integers N and K denoting the values mentioned in the statement above.
Output
For each test case, output a single line containing N space separated integers (which should be a permutation of [1..N], if Baahubali's soldiers can break all the forts. If it is not possible to break all the forts, output "1" (quotes for clarity).
Constraints
 1 ≤ T ≤ 1000
 1 ≤ N ≤ 10^{5}
 0 ≤ K ≤ N
 The sum of N over all test cases in a single test file will not exceed 10^{5}
Example
Input: 3 2 2 3 0 3 1 Output: 1 1 2 3 2 3 1
Explanation
For the first test case, N = 2 and K = 2. It is impossible to permute [1, 2] in any way such that abs(P[1]1) >= 2 and abs(P[2]2) >= 2. Hence, output is 1.
For the second test case, N = 3 and K = 0. We can just set P[i] = i, and hence the answer is 1 2 3
For the third case, the valid permutations are [2, 3, 1] and [3, 1, 2]. The answer is [2, 3, 1] since it is lexicographically smaller than [3, 1, 2].
Author:  suh_ash2008 
Editorial  http://discuss.codechef.com/problems/AMR15C 
Tags  acmamr15, constructive, greedy, implementation, medium, suh_ash2008 
Date Added:  11102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 