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。