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.


-----Input-----

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.


-----Output-----

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.


-----Examples-----
Input
4 5
2 3 1 4 4

Output
3 1 2 4 

Input
3 3
3 1 2

Output
-1



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:

import sys
#sys.stdin=open("data.txt")
input=sys.stdin.readline

n,m=map(int,input().split())

l=list(map(int,input().split()))
for i in range(len(l)):
    l[i]-=1

use=[0]*n
a=[0]*n
bad=0

for i in range(len(l)-1):
    # transfer l[i] to l[i+1]
    if a[l[i]] and a[l[i]]%n!=(l[i+1]-l[i])%n:
        bad=1
        break
    use[(l[i+1]-l[i])%n]=1
    a[l[i]]=(l[i+1]-l[i])%n
    if a[l[i]]==0: a[l[i]]=n

if not bad:
    # fill in gaps
    for i in range(n):
        if a[i]==0:
            for j in range(1,n+1):
                if not use[j%n]:
                    a[i]=j
                    use[j%n]=1
                    break
    if sum(use)==n:
        print(" ".join(map(str,a)))
    else:
        print("-1")
else:
    print("-1")

def calc(a,b,n):
	if(b<=a):
		return n-a+b
	else:
		return b-a

inp=input().split()
n=int(inp[0])
m=int(inp[1])
seq=[]
inp=input().split()
for val in inp:
	seq.append(int(val))
indices={}
flag=0
for i in range(len(seq)-1):
	hop=calc(seq[i],seq[i+1],n)
	if((seq[i] in indices) and indices[seq[i]]!=hop):
		print("-1")
		flag=1
		break
	indices[seq[i]]=hop
l=[]
for i in range(n+1):
	l.append(1)
flag2=0
if(flag==0):
	for i in range(1,n+1):
		try:
			val=indices[i]
		except:
			continue
		if(l[val]==1):
			l[val]=0
		else:
			print("-1")
			flag2=1
			break
	if(flag2==0):
		for i in range(1,n+1):
			try:
				print(indices[i],end=" ")
			except:
				j=1
				while(l[j]==0):
					j+=1
				print(j,end=" ")
				l[j]=0
		print()

n,m=map(int,input().split())
l=[]
l=list(map(int,input().split()))
a=[-1]*(n+1)
s=set()
sorry = False
for i in range(1,n+1):
    s.add(i)
for i in range(m-1):
    temp = (l[i+1] + n - l[i])%n
    if(temp == 0):
        temp = n
    #print(temp)
    if(a[l[i]] == -1 and temp in s):
        a[l[i]] = temp
        s.remove(temp)

    elif(a[l[i]] == temp):
        continue
    else:
        sorry=True
        break

if(sorry):
    print(-1)
else:
    ss = list(s)
    x=0
    for i in range(1,len(a)):
        if(a[i] == -1):
            a[i] = ss[x]
            x+=1
        print(a[i],"",end='')


def f(a,b,c):
	if (a-b+c)%c==0:
		return c
	else:
		return (a-b+c)%c
n,m=list(map(int,input().split()))
l=list(map(int,input().split()))
a=[0 for i in range(n)]
for i in range(m-1):
	if a[l[i]-1]==0 or a[l[i]-1]==f(l[i+1],l[i],n):
		a[l[i]-1]=f(l[i+1],l[i],n)
	else:
		print(-1)
		return
p=[i+1 for i in range(n)]
s=list(set(p)-set([i for i in a if i!=0]))
if len(s)!=a.count(0):
	print(-1)
	return
else:
	for i in range(n):
		if a[i]==0:
			a[i]=s[-1]
			s.pop()
for i in a:
	print(i,end=' ')

def main():
    n, m = map(int, input().split())
    l = list(map(int, input().split()))
    a = [0 for i in range(n)]
    for i in range(m - 1):
        d = l[i + 1] - l[i]
        if d <= 0:
            d += n
        if a[l[i] - 1] == 0:
            a[l[i] - 1] = d
        elif a[l[i] - 1] != d:
            return -1
    cnt = [0 for i in range(n + 1)]
    for i in a:
        cnt[i] += 1
    unused = set()
    for i in range(1, n + 1):
        if cnt[i] == 0:
            unused.add(i)
        elif cnt[i] > 1:
            return -1
    for i in range(n):
        if a[i] == 0:
            a[i] = unused.pop()
    return ' '.join(map(str, a))

print(main())

n, m = list(map(int, input().split()))
l = list(map(int, input().split()))
a = [0 for _ in range(n)]
f = [False for _ in range(n+1)]
ans = True
for i in range(m-1):
    for j in range(1, n+1):
        if (l[i] + j - 1)%n + 1 == l[i+1]:
            if a[l[i]-1] != 0 and a[l[i]-1] != j:
                ans = False
            else:
                if a[l[i]-1] == j:
                    break
                if f[j]:
                    ans = False
                f[j] = True
                a[l[i]-1] = j
            break
j = 1
for i in range(n):
    if not a[i]:
        while j <= n and f[j]:
            j += 1
        a[i] = j
        f[j] = True
if ans:
    print(*a)
else:
    print(-1)




n, m = [int(i) for i in input().split()]
l = [int(i) - 1 for i in input().split()]
ans = [-1] * n
for i in range(m - 1):
    t = (l[i + 1] - l[i]) % n
    if t == 0:
        t = n
    if ans[l[i]] != -1 and ans[l[i]] != t:
        print(-1)
        break
    ans[l[i]] = t
else:
    s = set()
    for i in ans:
        if i != -1:
            s.add(i)
    c = 1
    for i in range(n):
        if ans[i] == -1:
            while c in s:
                c += 1
            ans[i] = c
            s.add(c)

    if len(set(ans)) == n:
        print(' '.join([str(i) for i in ans]))
    else:
        print(-1)

n, m = list(map(int, input().split()))
a = list(map(int, input().split()))
ans = [0] * (n + 1)
for i in range(m - 1):
	pot = (a[i + 1] - a[i] + n) % n
	if pot == 0: pot = n
	if ans[a[i]] == 0 or ans[a[i]] == pot: ans[a[i]] = pot
	else:
		print(-1)
		return
used = [False] * (n + 1)
for i in ans:
	used[i] = True
for i in range(1, n + 1):
	if ans[i] == 0:
		for j in range(1, n + 1):
			if not used[j]:
				used[j] = True
				ans[i] = j
				break
print(' '.join(map(str, ans[1:])) if all(used[1:]) else -1)


n, m = map(int,input().split())
lm = list(map(int,input().split()))

impossible = False
an = [-1]*(n+1)
f = [False]*(n+1)
for k in range(m-1):
    if an[lm[k]] < 0:
        for i in range(1,n+1):
            if f[i]:
                continue
            x = lm[k]+i
            if x > n:
                x -= n
            if lm[k+1] != x:
                continue
            an[lm[k]] = i
            f[i] = True
            break
        if an[lm[k]] < 0:
            impossible = True
            break
    else:
        x = lm[k]+an[lm[k]]
        if x > n:
            x -= n
        if lm[k+1] != x:
            impossible = True
            break

if impossible:
    print(-1)
else:
    for i in range(1,n+1):
        if an[i] > 0:
            continue
        for j in range(1,n+1):
            if f[j]:
                continue
            an[i] = j
            f[j] = True
            break
    print(*an[1:])

n, m = list(map(int, input().split()))
l = [int(k) for k in input().split()]
a = [0]*n
for i in range(m-1):
    curLeader = l[i] - 1
    nextLeader = l[i+1] - 1
    jump = abs((nextLeader - curLeader) % n)
    if jump==0: jump = n
    a[curLeader] = jump

def reqNum(leader, jump):
    ans = (leader+jump)%n
    if(ans==0): ans = n
    return ans
def simulate():
    for i in range(m-1):
        leader = l[i]
        jump = a[leader-1]
        if(not reqNum(leader, jump)==l[i+1]): return False
    return True

if simulate():
    s = set(range(1,n+1)).difference(set(a))
    for i in range(n):
        if a[i]==0:
            a[i] = s.pop()
    t = sorted(a)
    if(t==list(range(1,n+1))): print(*a)
    else: print(-1)
else: print(-1)


input_ar = list(map(int,input().rstrip().split(" ")))
leaders = list(map(int,input().rstrip().split(" ")))
not_there_set = {i+1 for i in range(input_ar[0])}
a_n_done = [False for i in range(input_ar[0])]
a_n = [0 for i in range(input_ar[0])]
possible = True
for i in range(len(leaders) - 1):
    diff = leaders[i + 1] - leaders[i]
    if diff <= 0:
        diff += input_ar[0]
    if a_n[leaders[i] - 1] is 0:
        if diff in a_n:
            possible = False
            break
        not_there_set.remove(diff)
        a_n[leaders[i] - 1] = diff
    elif a_n[leaders[i] - 1] is not diff:
        possible = False
        break

if not possible:
    # print(a_n)
    print(-1)
else:
    # print('a_n is : {}'.format(a_n))
    for i in range(len(a_n)):
        if a_n[i] is 0:
            if len(not_there_set) <= 0:
                possible = False
                break
            a_n[i] = not_there_set.pop()
    if not possible:
        print(-1)
    else:
        for a in a_n:
            print('{} '.format(a), end='')
        print()

n, m = list(map(int, input().split()))
l = list(map(int, input().split()))
used = [False for _ in range(n + 1)]
ans = [0 for _ in range(n)]
f = True
for i in range(m - 1):
    d = ((l[i + 1] - l[i] + n - 1) % n) + 1
    if ans[l[i] - 1] == 0 and not used[d]:
        ans[l[i] - 1] = d
        used[d] = True
    elif ans[l[i] - 1] != d:
        f = False
        break

s = 0
j = 1
for i in range(n):
    while j < n and used[j]:
        j += 1
    if ans[i] == 0:
        ans[i] = j
        used[j] = True
    s += ans[i]

if s != n * (n + 1) // 2:
    f = False

idx = l[0] - 1
for i in range(m):
    if idx + 1 != l[i]:
        f = False
        break
    idx += ans[idx]
    idx %= n

if f:
    print(' '.join(list(map(str, ans))))
else:
    print(-1)


n, m = [int(i) for i in input().split()]
l = [int(i) for i in input().split()]
a = [0] * n

used = [0] * (n + 1)
cnt = 0

for i in range(len(l)-1):
    z = l[i+1] - l[i] 
    if z <= 0:
        z += n   
    if used[z] and a[l[i]-1] != z:
        print(-1)
        return
    a[l[i]-1] = z
    used[z] = 1
        
j = 1
for i in range(len(a)):
    if a[i] == 0:
        while used[j]:
            j+=1
            if j > n:
                print(-1)
                return
        a[i] = j
        used[j] = 1
        
if all(a) and all(used[1:]):
    print(*a)
else:
    print(-1)
        




def R():
    return list(map(int, input().split()))

n, m = R()
l = list(R())

a = [None] * n
b = [False] * n

c = set(range(1, n + 1))
for i in range(m - 1):
    j = l[i] - 1
    d = l[i + 1] - l[i]
    if d <= 0:
        d += n
    if a[j] != d:
        if a[j] is not None or b[d - 1]:
            print(-1)
            return
        a[j] = d
        b[d - 1] = True
        c.remove(d)
for i in range(n):
    if a[i] is None:
        a[i] = c.pop()
        
print(*a)


def R():
    return list(map(int, input().split()))

n, m = R()
l = list(R())

a = [None] * n
b = [False] * n

c = set(range(1, n + 1))
for i in range(m - 1):
    j = l[i] - 1
    d = l[i + 1] - l[i]
    if d <= 0:
        d += n
    if a[j] != d:
        if a[j] is not None or b[d - 1]:
            print(-1)
            break
        a[j] = d
        b[d - 1] = True
        c.remove(d)
else:
    for i in range(n):
        if a[i] is None:
            a[i] = c.pop()            
    print(*a)


def R():
    return list(map(int, input().split()))

n, m = R()
l = list(R())

a = [None] * n
b = [False] * n

for i in range(m - 1):
    j = l[i] - 1
    d = l[i + 1] - l[i]
    if d <= 0:
        d += n
    if a[j] != d:
        if a[j] is not None or b[d - 1]:
            print(-1)
            break
        a[j] = d
        b[d - 1] = True
else:
    j = 0
    for i in range(n):
        if a[i] is None:
            while b[j]:
                j += 1
            a[i] = j + 1
            j += 1
    print(*a)


def R():
    return list(map(int, input().split()))

n, m = R()
l = list(R())

a = [None] * n
b = [False] * n

for i in range(m - 1):
    j = l[i] - 1
    d = l[i + 1] - l[i]
    if d <= 0:
        d += n
    if a[j] != d:
        if a[j] is not None or b[d - 1]:
            print(-1)
            break
        a[j] = d
        b[d - 1] = True
else:
    j = 0
    for i in range(n):
        if a[i] is None:
            while b[j]:
                j += 1
            j += 1
            a[i] = j
    print(*a)


R=lambda:list(map(int, input().split()))
n,m=R()
l=list(R())
a=[None]*n
c =set(range(1, n + 1))
for i in range(m-1):
    j=l[i]-1
    d=l[i+1]-l[i]
    if d<=0:
        d+=n
    if a[j]!=d:
        if a[j] is not None or d not in c:
            print(-1)
            return
        a[j]=d
        c.remove(d)
for i in range(n):
    if a[i] is None:
        a[i]=c.pop()
print(*a)


I = lambda: list(map(int, input().split()))
n, m = I()
l = list(I())

res = [0] * (n + 1)
for i in range(m-1):
    new = (l[i+1] - l[i]) if l[i+1] - l[i] > 0 else (l[i+1] - l[i] + n)
    if res[l[i]] and res[l[i]] != new:
        print(-1)
        return
    else:
        res[l[i]] = new

wo0 = list(filter((0).__ne__, res))
if len(wo0) == len(set(wo0)):
    rest = set(range(1, n+1)) - set(wo0)
    res.pop(0)
    for x in rest:
        res[res.index(0)] = x
    print(*res)
else:
    print(-1)




n, m = list(map(int, input().split()))
l = list(map(int, input().split()))

a = [-1] * n

for i in range(m - 1):
    p = l[i + 1] - l[i]
    if p <= 0: p += n
    if a[l[i] - 1] != -1 and a[l[i] - 1] != p:
        print(-1)
        return
    a[l[i] - 1] = p

s = set(range(1, n + 1)) - set(i for i in a if i != -1)
for i in range(len(a)):
    if a[i] == -1:
        a[i] = s.pop()

if -1 in a or len(set(a)) != n:
    print(-1)
else:
    print(*a)


R=lambda:list(map(int,input().split()))
n,m=R()
l=list(R())
a=[None]*n
c =set(range(1, n + 1))
for i in range(m-1):
    j=l[i]-1
    d=l[i+1]-l[i]
    if d<=0:
        d+=n
    if a[j]!=d:
        if a[j] or d not in c:
            print(-1)
            return
        a[j]=d
        c.remove(d)
for i in range(n):
    if a[i] is None:
        a[i]=c.pop()
print(*a)


R=lambda:list(map(int,input().split()))
n,m=R()
l=list(R())
a=[None]*n
c=set(range(1, n + 1))
for i in range(m-1):
    j=l[i]-1
    d=l[i+1]-l[i]
    if d<=0:
        d+=n
    if a[j]!=d:
        if a[j] or d not in c:
            print(-1)
            return
        a[j]=d
        c.remove(d)
for i in range(n):
    if not a[i]:
        a[i]=c.pop()
print(*a)


def main():
    n, m = [int(item) for item in input().split()]
    l = [int(item) for item in input().split()]
    l = [0] + l
    a = [0] * (n + 1)
    
    for i in range(1, m):
        curr = (l[i + 1] - l[i] - 1) % n + 1
        if a[l[i]] != 0 and curr != a[l[i]]:return -1
        a[l[i]] = curr
    #print(a)
    cnt = [0] * (n + 1)
        
    for i in range(1, n + 1):
        cnt[a[i]] += 1
        if a[i] != 0 and cnt[a[i]] > 1:
            return -1

    if cnt[0] != 0:
        d = []
        for k in range(1, n + 1):
            if cnt[k] == 0:
                d.append(k)
        for i in range(1, n + 1):
            if a[i] == 0:
                a[i] = d[0]
                d.pop(0)

    return " ".join(str(x) for x in a[1:])
    
print(main())