Permutation Game

题面翻译

N个人，每轮leader报数，提供每一轮的leader，报的数字是这一轮的leader-上一轮的leader，每个数字只能被一个人报，每个人只能报一个数字

题目描述

$n$ children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation $a_{1},a_{2},...,a_{n}$ of length $n$ . It is an integer sequence such that each integer from $1$ to $n$ appears exactly once in it.

The game consists of $m$ steps. On each step the current leader with index $i$ counts out $a_{i}$ people in clockwise order, starting from the next person. The last one to be pointed at by the leader becomes the new leader.

You are given numbers $l_{1},l_{2},...,l_{m}$ — indices of leaders in the beginning of each step. Child with number $l_{1}$ is the first leader in the game.

Write a program which will restore a possible permutation $a_{1},a_{2},...,a_{n}$ . If there are multiple solutions then print any of them. If there is no solution then print -1.

输入格式

The first line contains two integer numbers $n$ , $m$ ( $1<=n,m<=100$ ).

The second line contains $m$ integer numbers $l_{1},l_{2},...,l_{m}$ ( $1<=l_{i}<=n$ ) — indices of leaders in the beginning of each step.

输出格式

Print such permutation of $n$ numbers $a_{1},a_{2},...,a_{n}$ that leaders in the game will be exactly $l_{1},l_{2},...,l_{m}$ if all the rules are followed. If there are multiple solutions print any of them.

If there is no permutation which satisfies all described conditions print -1.

样例 #1

样例输入 #1

4 5
2 3 1 4 4

样例输出 #1

3 1 2 4

样例 #2

样例输入 #2

3 3
3 1 2

样例输出 #2

-1

提示

Let's follow leadership in the first example:

• Child $2$ starts.
• Leadership goes from $2$ to $2+a_{2}=3$ .
• Leadership goes from $3$ to $3+a_{3}=5$ . As it's greater than $4$ , it's going in a circle to $1$ .
• Leadership goes from $1$ to $1+a_{1}=4$ .
• Leadership goes from $4$ to $4+a_{4}=8$ . Thus in circle it still remains at $4$ .