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

4 5
2 3 1 4 4

输出样例 #1

3 1 2 4 

输入样例 #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 $ .