← 返回题目列表

Codeforces · 1942/A

A. 农夫约翰的挑战

中文机器翻译题面 查看原题

如果 $$$a_1 \leq a_2 \leq \ldots \leq a_{n - 1} \leq a_{n}$$$,我们调用一个已排序的数组 $$$a$$$。

给你两个 Farmer John 最喜欢的整数,$$$n$$$ 和 $$$k$$$。他挑战你找到任何满足以下要求的数组 $$$a_1, a_2, \ldots, a_{n}$$$:

- $$$1 \leq a_i \leq 10^9$$$ 对于每个 $$$1 \leq i \leq n$$$;
- 在 $$$a$$$ 的 $$$n$$$ 总循环移位中,恰好 $$$k$$$ 已排序。$$$^\dagger$$$

如果不存在这样的数组$$$a$$$,则输出$$$-1$$$。

$$$^\dagger$$$数组 $$$a$$$ 的第 $$$x$$$ 个 ($$$1 \leq x \leq n$$$) 循环移位为 $$$a_x, a_{x+1} \ldots a_n, a_1, a_2 \ldots a_{x - 1}$$$。如果 $$$c_{x, i}$$$ 表示 $$$a$$$ 第 $$$x$$$ 个循环移位的第 $$$i$$$ 个元素,那么 $$$k$$$ 这样的 $$$x$$$ 应该满足 $$$c_{x,1} \leq c_{x,2} \leq \ldots \leq c_{x, n - 1} \leq c_{x, n}$$$。

例如,$$$a = [1, 2, 3, 3]$$$ 的循环移位如下:

- $$$x = 1$$$: $$$[1, 2, 3, 3]$$$(已排序);
- $$$x = 2$$$: $$$[2, 3, 3, 1]$$$(未排序);
- $$$x = 3$$$: $$$[3, 3, 1, 2]$$$(未排序);
- $$$x = 4$$$: $$$[3, 1, 2, 3]$$$(未排序)。

输入

第一行包含 $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — 测试用例的数量。

每个测试用例包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 10^3$$$) - $$$a$$$ 的长度和 $$$a$$$ 必须具有的排序循环移位数。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^3$$$。

输出

对于每个测试用例,打印一行:

- 如果存在有效数组$$$a$$$,则输出$$$n$$$个整数,分别代表$$$a_1, a_2, \ldots, a_{n}$$$;
- 否则,输出$$$-1$$$。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

3
2 2
3 1
3 2

输出 #1

1 1
69420 69 420
-1

注意

在第一个测试用例中,$$$a = [1, 1]$$$ 满足 $$$n = 2, k = 2$$$:

$$$a$$$ 的两个循环移位是 $$$[a_1, a_2]$$$ 和 $$$[a_2, a_1]$$$,它们都是 $$$[1, 1]$$$ 并且已排序。

在第二个测试用例中,$$$a = [69\,420, 69, 420]$$$ 满足 $$$n = 3, k = 1$$$:

$$$a$$$的三个循环移位分别是$$$[a_1,a_2,a_3]$$$,$$$[a_2,a_3,a_1]$$$,$$$[a_3,a_1,a_2]$$$,分别是$$$[69\,420,69,420]$$$,分别为 $$$[69, 420, 69\,420]$$$ 和 $$$[420, 69\,420, 69]$$$。

仅对 $$$[69, 420, 69\,420]$$$ 进行排序。