← 返回题目列表

Codeforces · 818/B

B. 排列游戏

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

n 个孩子围成一圈站着玩游戏。子数按顺时针顺序形成排列a1,a2,...,an,长度为n。它是一个整数序列,从 1 到 n 的每个整数在其中恰好出现一次。

游戏由 m 个步骤组成。在每一步中,索引为 i 的当前领导者从下一个人开始按顺时针顺序数出 ai 人。最后被领导指向的人成为新的领导。

您将获得数字 l1、l2、...、lm — 每一步开始时的领导者索引。编号为 l1 的孩子是游戏中的第一位领导者。

编写一个程序来恢复可能的排列 a1, a2, ..., an。如果有多个解决方案,则打印其中任何一个。如果无解则打印-1。

输入

第一行包含两个整数 n, m (1 ≤ n, m ≤ 100)。

第二行包含 m 个整数 l1, l2, ..., lm (1 ≤ li ≤ n) — 每个步骤开始时的领导者索引。

输出

打印 n 个数字 a1, a2, ..., an 的排列,如果遵循所有规则,游戏中的领导者将恰好是 l1, l2, ..., lm。如果有多个解决方案,请打印其中任何一个。

如果没有满足所有描述条件的排列,则打印 -1。

示例

输入 #1

4 5
2 3 1 4 4

输出 #1

3 1 2 4

输入 #2

3 3
3 1 2

输出 #2

-1

注意

让我们跟随第一个示例中的领导:

- 子级 2 启动。
- 领导力从 2 变为 2 + a2 = 3。
- 领导力从 3 变为 3 + a3 = 5。由于它大于 4,所以会循环到 1。
- 领导力从 1 变为 1 + a1 = 4。
- 领导力从 4 变为 4 + a4 = 8。因此在循环中它仍然保持在 4。