← 返回题目列表

Codeforces · 2225/G

G. 简单的问题

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

有一天,Polycarp 提出了以下简单问题:给出数字 $$$0, 1, \ldots, n-1$$$。是否可以将它们排列成使得每对相邻数字的绝对差至少可以被数字 $$$k_1, k_2, \ldots, k_m$$$ 整除?

波利卡普花了很长时间思考如何解决这个问题,最终发现事情并没有那么简单。帮他解决这个问题。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$3 \leq n \leq 5 \cdot 10^{3}$$$; $$$1 \leq m \leq 10$$$)。

每个测试用例的第二行包含 $$$m$$$ 整数 $$$k_{i}$$$ ($$$1 \leq k_i \leq \left\lfloor \frac{n}{3} \right\rfloor$$$)。

输入的附加限制:

  • 所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^{3}$$$。

输出

对于每个测试用例,输出以下内容之一: 如果不存在合适的排列,则

  • -1 在单行上;
  • $$$n$$$ 整数 $$$0, 1, \ldots, n-1$$$ 满足条件。如果有多个答案,请打印其中任何一个。

示例

输入
复制

2
10 2
2 3
6 1
2

输出
复制

0 2 6 8 4 1 3 5 7 9
-1