818B.md (2063B)
1 Source: https://codeforces.com/problemset/problem/818/B 2 3 B. Permutation Game 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 *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. 22 23 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. 24 25 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. 26 27 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. 28 29 Input 30 31 The first line contains two integer numbers *n*, *m* (1 ≤ *n*, *m* ≤ 100). 32 33 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. 34 35 Output 36 37 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. 38 39 If there is no permutation which satisfies all described conditions print -1. 40 41 Examples 42 43 Input 44 45 ``` 46 4 5 47 2 3 1 4 4 48 ``` 49 50 Output 51 52 ``` 53 3 1 2 4 54 ``` 55 56 Input 57 58 ``` 59 3 3 60 3 1 2 61 ``` 62 63 Output 64 65 ``` 66 -1 67 ``` 68 69 Note 70 71 Let's follow leadership in the first example: 72 73 * Child 2 starts. 74 * Leadership goes from 2 to 2 + *a*2 = 3. 75 * Leadership goes from 3 to 3 + *a*3 = 5. As it's greater than 4, it's going in a circle to 1. 76 * Leadership goes from 1 to 1 + *a*1 = 4. 77 * Leadership goes from 4 to 4 + *a*4 = 8. Thus in circle it still remains at 4.