n children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation a₁, a₂, ..., 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₁, l₂, ..., l_m — indices of leaders in the beginning of each step. Child with number l₁ is the first leader in the game.

Write a program which will restore a possible permutation a₁, a₂, ..., a_n. If there are multiple solutions then print any of them. If there is no solution then print -1.

Input

The first line contains two integer numbers n, m (1 ≤ n, m ≤ 100).

The second line contains m integer numbers l₁, l₂, ..., l_m (1 ≤ l_i ≤ n) — indices of leaders in the beginning of each step.

Output

Print such permutation of n numbers a₁, a₂, ..., a_n that leaders in the game will be exactly l₁, l₂, ..., 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.

Note

Let's follow leadership in the first example:

Child 2 starts.
Leadership goes from 2 to 2 + a₂ = 3.
Leadership goes from 3 to 3 + a₃ = 5. As it's greater than 4, it's going in a circle to 1.
Leadership goes from 1 to 1 + a₁ = 4.
Leadership goes from 4 to 4 + a₄ = 8. Thus in circle it still remains at 4.

Permutation Game

Examples