A. Farmer John's Challenge
constructive algorithms; math
Trade Winds - Patrick Deng⠀Let's call an array \(a\) sorted if \(a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}\).You are given two of Farmer John's favorite integers, \(n\) and \(k\). He challenges you to find any array \(a_1, a_2, \ldots, a_{n}\) satisfying the following requirements: \(1 \leq a_i \leq 10^9\) for each \(1 \leq i \leq n\); Out of the \(n\) total cyclic shifts of \(a\), exactly \(k\) of them are sorted.\(^\dagger\) If there is no such array \(a\), output \(-1\).\(^\dagger\)The \(x\)-th (\(1 \leq x \leq n\)) cyclic shift of the array \(a\) is \(a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}\). If \(c_{x, i}\) denotes the \(i\)'th element of the \(x\)'th cyclic shift of \(a\), exactly \(k\) such \(x\) should satisfy \(c_{x,1} \leq c_{x,2} \leq \ldots \leq c_{x, n - 1} \leq c_{x, n}\).For example, the cyclic shifts for \(a = [1, 2, 3, 3]\) are the following: \(x = 1\): \([1, 2, 3, 3]\) (sorted); \(x = 2\): \([2, 3, 3, 1]\) (not sorted); \(x = 3\): \([3, 3, 1, 2]\) (not sorted); \(x = 4\): \([3, 1, 2, 3]\) (not sorted).
The first line contains \(t\) (\(1 \leq t \leq 10^3\)) — the number of test cases.Each test case contains two integers \(n\) and \(k\) (\(1 \leq k \leq n \leq 10^3\)) — the length of \(a\) and the number of sorted cyclic shifts \(a\) must have.It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^3\).
For each test case, print a single line: if there is a valid array \(a\), output \(n\) integers, representing \(a_1, a_2, \ldots, a_{n}\); otherwise, output \(-1\). If there are multiple solutions, print any of them.
In the first testcase, \(a = [1, 1]\) satisfies \(n = 2, k = 2\):The two cyclic shifts of \(a\) are \([a_1, a_2]\) and \([a_2, a_1]\), which are both \([1, 1]\) and are sorted.In the second testcase, \(a = [69\,420, 69, 420]\) satisfies \(n = 3, k = 1\):The three cyclic shifts of \(a\) are \([a_1, a_2, a_3]\), \([a_2, a_3, a_1]\), \([a_3, a_1, a_2]\), which are \([69\,420, 69, 420]\), \([69, 420, 69\,420]\), and \([420, 69\,420, 69]\), respectively. Only \([69, 420, 69\,420]\) is sorted.