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: MEDIUM_HARD
Tags: Implementation

Starter code:

Solutions:
read = lambda : map(int, input().split())
(n, m) = read()
l = list(read())
a = [0] * (n + 1)

def fail():
	print(-1)
	exit()
for i in range(m - 1):
	pr = -1
	if a[l[i]]:
		pr = a[l[i]]
	a[l[i]] = (l[i + 1] - l[i]) % n
	if a[l[i]] == 0:
		a[l[i]] = n
	if pr != -1 and pr != a[l[i]]:
		fail()
s = set(a)
mex = 0
for i in range(1, n + 1):
	if not a[i]:
		while mex in s:
			mex += 1
		a[i] = mex
		s.add(mex)
p = [i for i in range(1, n + 1)]
if sorted(a[1:]) != p:
	fail()
print(*a[1:])


R = lambda : 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)
			exit()
		a[j] = d
		c.remove(d)
for i in range(n):
	if not a[i]:
		a[i] = c.pop()
print(*a)


from sys import exit
(n, m) = 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)
		exit(0)
	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)


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)


inp = input()
(n, m) = [int(x) for x in inp.split(' ')]
inp = input()
a = [int(x) for x in inp.split(' ')]
ok = 1
perm = [0 for i in range(n + 1)]
used = [0 for i in range(n + 1)]
for i in range(m - 1):
	ai = a[i + 1] - a[i]
	if ai <= 0:
		ai += n
	if used[ai] and used[ai] != a[i]:
		ok = 0
	used[ai] = a[i]
	if perm[a[i]] and perm[a[i]] != ai:
		ok = 0
	perm[a[i]] = ai
j = 1
for i in range(1, n + 1):
	while j < n and used[j]:
		j += 1
	if perm[i] == 0:
		perm[i] = j
		used[j] = i
if ok == 0:
	print(-1)
else:
	print(' '.join([str(x) for x in perm[1:]]))


import sys
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):
	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:
	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')


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
a = [0] * (n + 1)
b = set()
f = True
for i in range(m - 1):
	if (l[i + 1] - l[i]) % n == 0:
		x = n
	else:
		x = (l[i + 1] - l[i]) % n
	if x in b and a[l[i]] != x or (a[l[i]] != 0 and a[l[i]] != x):
		f = False
	else:
		a[l[i]] = x
		b.add(x)
for i in range(1, n + 1):
	if a[i] == 0:
		for j in range(1, n + 1):
			if j not in b:
				a[i] = j
				b.add(j)
				break
if f:
	for i in range(1, n + 1):
		print(a[i], end=' ')
else:
	print(-1)


from __future__ import division, print_function
from sys import stdin, stdout
import itertools, os, sys, threading
from collections import deque, Counter, OrderedDict, defaultdict
import heapq
from math import ceil, floor, log, sqrt, factorial, pow, pi, gcd

def ii():
	return int(input())

def si():
	return str(input())

def mi():
	return map(int, input().split())

def li():
	return list(mi())

def fii():
	return int(stdin.readline())

def fsi():
	return str(stdin.readline())

def fmi():
	return map(int, stdin.readline().split())

def fli():
	return list(fmi())
abc = 'abcdefghijklmnopqrstuvwxyz'
abd = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}
mod = 1000000007
(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])

def getKey(item):
	return item[0]

def sort2(l):
	return sorted(l, key=getKey)

def d2(n, m, num):
	return [[num for x in range(m)] for y in range(n)]

def isPowerOfTwo(x):
	return x and (not x & x - 1)

def decimalToBinary(n):
	return bin(n).replace('0b', '')

def ntl(n):
	return [int(i) for i in str(n)]

def powerMod(x, y, p):
	res = 1
	x %= p
	while y > 0:
		if y & 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res

def gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x
graph = defaultdict(list)
visited = [0] * 1000000
col = [-1] * 1000000

def dfs(v, c):
	if visited[v]:
		if col[v] != c:
			print('-1')
			exit()
		return
	col[v] = c
	visited[v] = 1
	for i in graph[v]:
		dfs(i, c ^ 1)

def bfs(d, v):
	q = []
	q.append(v)
	visited[v] = 1
	while len(q) != 0:
		x = q[0]
		q.pop(0)
		for i in d[x]:
			if visited[i] != 1:
				visited[i] = 1
				q.append(i)
		print(x)
	print(l)

def make_graph(e):
	d = {}
	for i in range(e):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
		if y not in d.keys():
			d[y] = [x]
		else:
			d[y].append(x)
	return d

def gr2(n):
	d = {}
	for i in range(n):
		(x, y) = mi()
		if x not in d.keys():
			d[x] = [y]
		else:
			d[x].append(y)
	return d

def connected_components(graph):
	seen = set()

	def dfs(v):
		vs = set([v])
		component = []
		while vs:
			v = vs.pop()
			seen.add(v)
			vs |= set(graph[v]) - seen
			component.append(v)
		return component
	ans = []
	for v in graph:
		if v not in seen:
			d = dfs(v)
			ans.append(d)
	return ans
(n, m) = mi()
l = li()
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)
			exit()
		a[j] = d
		c.remove(d)
for i in range(n):
	if not a[i]:
		a[i] = c.pop()
print(*a)


from collections import defaultdict
(N, M) = map(int, input().split())
L = list(map(int, input().split()))
A = [-1 for _ in range(N)]
U = defaultdict(bool)

def solve():
	for i in range(M - 1):
		cur = L[i] - 1
		nxt = L[i + 1] - 1
		delta = (nxt - cur) % N if nxt != cur else N
		if A[cur] == -1 or A[cur] == delta:
			A[cur] = delta
			U[delta] = True
		else:
			return False
	RA = [i for (i, a) in enumerate(A) if a == -1]
	RU = [i for i in range(1, N + 1) if not U[i]]
	if len(RA) != len(RU):
		return False
	for (i, j) in zip(RA, RU):
		A[i] = j
		U[j] = True
	return True
if not solve():
	print('-1')
else:
	print(' '.join(map(str, A)))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
a = [-1] * (n + 1)
s = [True] + [False] * n
for i in range(m - 1):
	curr = l[i + 1] - l[i]
	if curr <= 0:
		curr += n
	if a[l[i]] == curr:
		continue
	if s[curr] or a[l[i]] != -1:
		print('-1')
		exit()
	s[curr] = True
	a[l[i]] = curr
for (i, x) in enumerate(a[1:]):
	if x == -1:
		for j in range(len(s)):
			if s[j] == False:
				s[j] = True
				a[i + 1] = j
				break
print(' '.join((str(x) for x in a[1:])))


(n, m) = list(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))
per = [-1] * n
flag = True
for el in range(m - 1):
	i = a[el] - 1
	j = a[el + 1] - 1
	res = (j - i) % n
	if res == 0:
		res = n
	if per[i] == -1:
		per[i] = res
	elif per[i] == res:
		pass
	else:
		flag = False
b = []
for el in per:
	if el == -1:
		pass
	else:
		b.append(el)
if len(set(b)) != len(b):
	flag = False
for i in range(n):
	if per[i] == -1:
		for j in range(1, n + 1):
			if j not in b:
				per[i] = j
				b.append(j)
				break
if flag:
	print(' '.join(map(str, per)))
else:
	print(-1)


(n, m) = map(int, input().split())
ans = [None] * n
l = list(map(int, input().split()))
for i in range(1, m):
	d = (l[i] - l[i - 1]) % n
	if d == 0:
		d += n
	if ans[l[i - 1] - 1] == None or ans[l[i - 1] - 1] == d:
		ans[l[i - 1] - 1] = d
	else:
		print(-1)
		quit()
l = [i + 1 for i in range(n)]
for i in ans:
	if i in l:
		l.remove(i)
	elif i != None:
		print(-1)
		quit()
for i in ans:
	if i == None:
		print(l[-1], end=' ')
		l.pop()
	else:
		print(i, end=' ')


(n, m) = 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) = 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)


(n, m) = [int(number) for number in input().split()]
indices = [int(number) for number in input().split()]
res = [0] * (n + 1)
kids = {i for i in range(1, n + 1)}
current = indices[0]
flag = False
for (i, index) in enumerate(indices[1:]):
	a = index - current if index > current else n - current + index
	if a in kids:
		kids.remove(a)
	if res[current] != 0 and res[current] != a:
		print(-1)
		exit()
	res[current] = a
	current = index
for i in range(1, n + 1):
	if res[i] == 0:
		res[i] = kids.pop() if len(kids) != 0 else 1
if len(set(res[1:])) != n:
	print(-1)
	exit()
for i in res[1:]:
	print(i, end=' ')


(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
	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 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) = input().split(' ')
L = input().split(' ')
(n, m) = (int(n), int(m))
for i in range(m):
	L[i] = int(L[i])
A = [-1] * n
used = [0] * n
ind = 1
for i in range(m - 1):
	step = (L[i + 1] - L[i]) % n
	if step == 0:
		step = n
	if A[L[i] - 1] == -1 and used[step - 1] == 0:
		A[L[i] - 1] = step
		used[step - 1] = 1
	elif A[L[i] - 1] == step:
		continue
	else:
		ind = 0
		break
if ind == 0:
	print(-1)
else:
	indused = 0
	for i in range(n):
		if A[i] == -1:
			while used[indused] == 1:
				indused += 1
			A[i] = indused + 1
			indused += 1
		print(A[i], end=' ')


from random import randint
(n, m) = map(int, input().split())
a = [int(x) for x in input().split()]
digits = list(range(1, n + 1))
res = [0] * n
flag = 0
cycle = 0
for i in range(m - 1):
	if cycle != 0:
		if a[i + 1] != cycle:
			flag = 1
	if a[i + 1] == a[i] and cycle == 0:
		cycle = a[i + 1]
	if a[i + 1] <= a[i]:
		d = a[i + 1] + n - a[i]
	else:
		d = a[i + 1] - a[i]
	if d % n == 0:
		d = n
	if res[a[i] - 1] == 0:
		res[a[i] - 1] = d
	elif res[a[i] - 1] != d:
		flag = 1
for i in res:
	if i in digits:
		digits.remove(i)
for i in range(len(res)):
	if res[i] == 0:
		s = digits[randint(0, len(digits) - 1)]
		res[i] = s
		digits.remove(s)
if sorted(res) != list(range(1, n + 1)) or flag:
	print(-1)
else:
	print(*res)


a = list(map(int, input().split()))
b = list(map(int, input().split()))
h1 = list(range(1, a[0] + 1))
h = a[0] * [-1]
y = 0
for i in range(a[1] - 1):
	try:
		if h[b[i] - 1] != -1:
			s = b[i + 1] - b[i]
			if s <= 0:
				s += a[0]
			if s != h[b[i] - 1]:
				y = 1
				print(-1)
				break
		h[b[i] - 1] = b[i + 1] - b[i]
		if h[b[i] - 1] <= 0:
			h[b[i] - 1] += a[0]
	except:
		y = 1
		print(-1)
		break
if y == 0:
	d1 = set(h1)
	d2 = set(h)
	d3 = d2 & d1
	d4 = list(d1 - d3)
	if len(d4) != h.count(-1):
		print(-1)
	else:
		j = 0
		for i in range(a[0]):
			if h[i] == -1:
				h[i] = d4[j]
				j = j + 1
			print(h[i], end=' ')


from sys import stdin, stdout
(n, m) = map(int, stdin.readline().split())
position = list(map(int, stdin.readline().split()))
ans = [0 for i in range(n + 1)]
used = set()
label = 1
for i in range(m - 1):
	if not ans[position[i]]:
		if not position[i + 1] - position[i]:
			ans[position[i]] = n
			if n not in used:
				used.add(n)
			else:
				label = 0
		else:
			ans[position[i]] = (position[i + 1] - position[i]) % n
			if (position[i + 1] - position[i]) % n not in used:
				used.add((position[i + 1] - position[i]) % n)
			else:
				label = 0
	elif position[i + 1] - position[i] and ans[position[i]] != (position[i + 1] - position[i]) % n:
		label = 0
	elif not position[i + 1] - position[i] and ans[position[i]] != n:
		label = 0
position = []
for i in range(1, n + 1):
	if not ans[i]:
		position.append(i)
if label:
	for i in range(1, n + 1):
		if i not in used:
			ans[position.pop()] = i
if not label:
	stdout.write('-1')
else:
	stdout.write(' '.join(list(map(str, ans[1:]))))


(n, k) = map(int, input().split())
l = list(map(int, input().split()))
for i in range(k - 1):
	l[i] = [l[i], l[i + 1] - l[i] + n * (l[i + 1] <= l[i])]
a = l.pop()
l = sorted(l) + [[1000, 1000]]
f = 1
c = []
for i in range(k - 1):
	if l[i][0] == l[i + 1][0] and l[i][1] != l[i + 1][1] or (l[i][0] != l[i + 1][0] and l[i][1] == l[i + 1][1]):
		f = 0
		print(-1)
		break
	elif l[i][0] != l[i + 1][0]:
		c.append(l[i])
if f:
	z = []
	c.append([1000, 1000])
	fz = []
	for i in range(len(c)):
		fz.append([c[i][1], c[i][0]])
	fz = sorted(fz) + [[1000, 1000]]
	lch = []
	for i in range(len(l)):
		lch.append([l[i][1], l[i][0]])
	lch = sorted(lch)
	for i in range(k - 1):
		if lch[i][0] == lch[i + 1][0] and lch[i][1] != lch[i + 1][1] or (lch[i][0] != lch[i + 1][0] and lch[i][1] == lch[i + 1][1]):
			f = 0
			print(-1)
			break
	if f:
		fz.pop()
		(i, j) = (0, 0)
		while i + j < n:
			if fz[i][0] != i + j + 1:
				j += 1
				z.append(i + j)
			else:
				i += 1
		j = 0
		for i in range(n):
			if i + 1 == c[j][0]:
				print(c[j][1], end=' ')
				j += 1
			else:
				print(z[i - j], end=' ')


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) = map(int, input().split())
l = list(map(int, input().split()))
a = [-1] * n
s = set(range(1, n + 1))
d = set()
for i in range(m - 1):
	for j in range(1, n + 1):
		if (l[i] + j - l[i + 1]) % n == 0:
			if j in d and a[l[i] - 1] != j:
				print(-1)
				exit()
			a[l[i] - 1] = j
			d.add(j)
			break
b = list(s - s.intersection(d))
k = 0
for i in range(n):
	if a[i] == -1:
		if k == len(b):
			print(-1)
			exit()
		a[i] = b[k]
		k += 1
print(*a)


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)
		exit(0)
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)
	exit(0)
else:
	for i in range(n):
		if a[i] == 0:
			a[i] = s[-1]
			s.pop()
for i in a:
	print(i, end=' ')


(n, m) = map(int, input().split())
p = [0] * (n + 1)
seen = p.copy()
l = list(map(int, input().split()))
cnt = 0
for i in range(m - 1):
	d = (l[i + 1] - l[i] + n) % n
	d = d if d != 0 else n
	if seen[d] == 1 and p[l[i]] != d:
		print(-1)
		quit()
	cnt += 1 if seen[d] == 0 else 0
	p[l[i]] = d
	seen[d] = 1
(i, j) = (1, 1)
while i <= n:
	if p[i] != 0:
		i += 1
		continue
	while j < n and seen[j] == 1:
		j += 1
	p[i] = j
	seen[j] = 1
	cnt += 1
	i += 1
ans = [str(p[i]) for i in range(1, n + 1)]
print(' '.join(ans) if cnt == n else -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)


import sys
from bisect import bisect_left as lb
from collections import deque
from queue import PriorityQueue as pq
from math import *
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7
(n, k) = il()
a = il()
ans = [-1 for i in range(n)]
x = a[0] - 1
d = {}
vis = [i for i in range(1, n + 1)]
for i in range(k - 1):
	t = a[i + 1] - a[i]
	if t <= 0:
		t += n
	if ans[a[i] - 1] != t:
		if ans[a[i] - 1] >= 0 or d.get(t):
			print(-1)
			exit(0)
		ans[a[i] - 1] = t
		d[t] = 1
		vis.remove(t)
for i in range(n):
	if ans[i] == -1:
		ans[i] = vis.pop()
print(*ans)


(n, m) = [int(x) for x in input().split()]
l = [int(x) for x in input().split()]
a = [-1] * (n + 1)
t = True
d1 = set()
d = {}
for x in range(len(l) - 1):
	if l[x + 1] - l[x] == 0:
		if a[l[x]] != -1 and a[l[x]] != n:
			t = False
		d1.add(n)
		if n in d:
			if d[n] != l[x]:
				t = False
		else:
			d[n] = l[x]
		a[l[x]] = n
	elif l[x + 1] - l[x] < 0:
		if a[l[x]] != -1 and a[l[x]] != n + l[x + 1] - l[x]:
			t = False
		if n + l[x + 1] - l[x] in d:
			if d[n + l[x + 1] - l[x]] != l[x]:
				t = False
		else:
			d[n + l[x + 1] - l[x]] = l[x]
		d1.add(n + l[x + 1] - l[x])
		a[l[x]] = n + l[x + 1] - l[x]
	else:
		if a[l[x]] != -1 and a[l[x]] != l[x + 1] - l[x]:
			t = False
		if l[x + 1] - l[x] in d:
			if d[l[x + 1] - l[x]] != l[x]:
				t = False
		else:
			d[l[x + 1] - l[x]] = l[x]
		d1.add(l[x + 1] - l[x])
		a[l[x]] = l[x + 1] - l[x]
if t == False:
	print(-1)
else:
	p = set([x for x in range(1, n + 1)])
	p -= d1
	for x in range(1, n + 1):
		if a[x] == -1:
			print(p.pop(), end=' ')
			continue
		print(a[x], end=' ')


(n, m) = map(int, input().split())
L = list(map(int, input().split()))
a = [-1] * n
el = set(range(1, n + 1))
for i in range(m - 1):
	step = L[i + 1] - L[i]
	if step <= 0:
		step += n
	if a[L[i] - 1] != step:
		if a[L[i] - 1] >= 0 or step not in el:
			print(-1)
			exit(0)
		a[L[i] - 1] = step
		el.remove(step)
for i in range(n):
	if a[i] == -1:
		a[i] = el.pop()
print(*a)


(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)


(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)


def R():
	return 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)
			exit()
		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)


(n, m) = [int(x) for x in input().split()]
mm = [int(x) for x in input().split()]
a = [0] * (n + 1)
f = False
for i in range(m - 1):
	r = mm[i + 1] - mm[i]
	if r <= 0:
		r += n
	if a[mm[i]] == 0:
		a[mm[i]] = r
	elif a[mm[i]] != r:
		f = True
		break
unused = []
for i in range(1, n + 1):
	if a.count(i) > 1:
		f = True
		break
	elif a.count(i) == 0:
		unused.append(i)
if f:
	print(-1)
else:
	res = []
	for i in range(1, n + 1):
		if a[i] == 0:
			res.append(unused.pop())
		else:
			res.append(a[i])
	print(*res)


def read():
	return [int(x) for x in input().split(' ')]
(n, m) = read()
I = read()
a = [-1] * (n + 1)
for i in range(m - 1):
	current = I[i]
	next = I[i + 1]
	val = next - current if next - current > 0 else next - current + n
	if val in a and a[I[i]] != val:
		print('-1')
		break
	elif a[I[i]] != -1 and a[I[i]] != val:
		print('-1')
		break
	a[I[i]] = val
else:
	j = []
	for num in range(1, n + 1):
		if num not in a:
			j.append(num)
	k = 0
	for (i, num) in enumerate(a[1:]):
		if num == -1:
			a[i + 1] = j[k]
			k += 1
	print(' '.join(map(str, a[1:])))


[n, m] = map(int, input().strip().split())
lis = list(map(int, input().strip().split()))

def solve():
	res = [0 for _ in range(n)]
	used = [False for _ in range(n)]
	for (l0, l1) in zip(lis, lis[1:]):
		al0 = n - (l0 - l1) % n
		if res[l0 - 1] != 0 and res[l0 - 1] != al0 or (res[l0 - 1] == 0 and used[al0 - 1]):
			return [-1]
		res[l0 - 1] = al0
		used[al0 - 1] = True
	i0s = [i for (i, a) in enumerate(res) if a == 0]
	not_used = list(set(range(1, n + 1)) - set(res))
	for (i, a) in zip(i0s, not_used):
		res[i] = a
	return res
res = solve()
print(' '.join(map(str, res)))


f = lambda : map(int, input().split())
(n, m) = f()
p = list(f())
s = set(range(1, n + 1))
t = [0] * n
for (x, y) in zip(p, p[1:]):
	q = (y - x) % n
	if not q:
		q = n
	if t[x - 1] == q:
		continue
	if t[x - 1] or q not in s:
		print(-1)
		exit()
	t[x - 1] = q
	s.remove(q)
for q in t:
	print(q if q else s.pop())


(n, m) = list(map(int, input().split()))
l = list(map(int, input().split()))
l2 = [0 for i in range(1, n + 1)]

def fill():
	for i in range(1, n + 1):
		if not i in l2:
			return i
for i in range(m - 1):
	added = l[i + 1] - l[i]
	if added <= 0:
		added += n
	l2[l[i] - 1] = added
for i in range(n):
	if l2[i] == 0:
		l2[i] = fill()
l3 = [0] * 100
for i in range(n):
	l3[l2[i] - 1] += 1

def f():
	for i in range(n):
		if l3[i] > 1:
			print(-1)
			return
	ind = l[0] - 1
	lead = l2[ind]
	for i in range(m - 1):
		ind = (ind + lead) % n
		lead = l2[ind]
		if ind + 1 != l[i + 1]:
			print(-1)
			return
	for i in range(n):
		print(l2[i], end=' ')
f()


def main():
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(m):
		l[i] -= 1
	a = [-1 for i in range(n)]
	now = l[0]
	for i in range(1, m):
		if a[now] == -1:
			for j in range(1, n + 1):
				if (now + j) % n == l[i]:
					a[now] = j
					break
		now = (now + a[now]) % n
		if now != l[i]:
			print(-1)
			return
	ct = [0 for i in range(n + 1)]
	for i in range(n):
		if a[i] > 0:
			ct[a[i]] += 1
			if ct[a[i]] > 1:
				print(-1)
				return
	idx = 1
	for i in range(n):
		while idx <= n and ct[idx] != 0:
			idx += 1
		if a[i] == -1:
			if idx > n:
				print(-1)
				return
			a[i] = idx
			ct[idx] += 1
	print(' '.join(map(str, a)))
main()


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
	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())


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(-1)
else:
	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()


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) = [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)


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


(n, m) = 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) = map(int, input().split())
L = [int(x) - 1 for x in input().split()]
A = [-1 for _ in range(n)]
N = set(range(n))
good = True
x = L[0]
for q in L[1:]:
	dist = (q + n - x) % n
	if A[x] == -1:
		if dist in N:
			A[x] = dist
			N.remove(dist)
		else:
			good = False
	elif A[x] != dist:
		good = False
	x = q
for i in range(len(A)):
	if A[i] == -1:
		A[i] = N.pop()
if good:
	print(' '.join(map(lambda x: str(n if x == 0 else x), A)))
else:
	print(-1)


def list_input():
	return list(map(int, input().split()))
[n, m] = list_input()
l = list_input()
a = [-1 for i in range(n)]
used = [0 for i in range(n + 1)]
for i in range(m - 1):
	id = l[i] - 1
	dist = l[i + 1] - l[i]
	if dist <= 0:
		dist += n
	if a[id] > -1 and a[id] != dist or (a[id] == -1 and used[dist] == 1):
		print('-1')
		exit(0)
	a[id] = dist
	used[dist] = 1
k = 1
for i in range(n):
	if a[i] == -1:
		while k <= n and used[k] > 0:
			k += 1
		a[i] = k
		k += 1
print(' '.join(map(str, a)))


from sys import exit
(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)
		exit(0)
	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)
				exit(0)
		a[i] = j
		used[j] = 1
if all(a) and all(used[1:]):
	print(*a)
else:
	print(-1)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
used = [0] * (n + 1)
ans = [0] * (n + 1)
for (x, y) in zip(a, a[1:]):
	z = (y - x) % n or n
	if ans[x] == 0 and used[z] or (ans[x] != 0 and ans[x] != z):
		print(-1)
		exit()
	used[z] = 1
	ans[x] = z
i = 1
for j in range(1, n + 1):
	if ans[j] == 0:
		while used[i]:
			i += 1
		ans[j] = i
		i += 1
print(*ans[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) = map(int, input().split())
l = list(map(int, input().split()))
ans = [None] + [0] * n
check = 0
d = {}
cans = {}
dans = {}
for i in range(m):
	if l[i] > n:
		l[i] = l[i] % n
for i in range(m - 1):
	d = l[i + 1] - l[i]
	if d < 0:
		d = l[i + 1] + n - l[i]
		l[i + 1] = (l[i + 1] + n) % n
	elif d == 0:
		d = n
	if d not in ans:
		if l[i] not in dans:
			dans[l[i]] = d
			ans[l[i]] = d
			cans[d] = l[i]
		else:
			check = 1
			break
	elif l[i] != cans[d]:
		check = 1
		break
if check == 0:
	j = 0
	for i in range(1, n + 1):
		while ans[j] != 0 and j != n:
			j += 1
		if i not in cans:
			ans[j] = i
	if ans.count(0) != 0:
		print(-1)
	else:
		print(*ans[1:])
else:
	print(-1)


(n, m) = map(int, input().split())
V = list(map(int, input().split()))
G = []
I = []
for i in range(n + 1):
	G.append(0)
	I.append(0)
for i in range(m - 1):
	tmp = (V[i + 1] - V[i] + 2 * n) % n
	if tmp == 0:
		tmp = n
	if I[V[i]] != tmp and I[V[i]]:
		print(-1)
		exit()
	I[V[i]] = tmp
	if G[tmp] != 0 and G[tmp] != V[i]:
		print(-1)
		exit()
	G[tmp] = V[i]
cnt = 1
for i in range(n):
	if I[i + 1] == 0:
		while G[cnt] != 0:
			cnt += 1
		I[i + 1] = cnt
		G[cnt] = i + 1
for i in range(n):
	print(I[i + 1], end=' ')
print()


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
mark = {}
a = [-1] * n
for i in range(m - 1):
	temp = l[i + 1] - l[i]
	if l[i + 1] - l[i] <= 0:
		temp += n
	if a[l[i] - 1] == temp:
		continue
	if a[l[i] - 1] == -1:
		a[l[i] - 1] += temp + 1
		if a[l[i] - 1] not in mark:
			mark[a[l[i] - 1]] = 1
		else:
			print('-1')
			break
	else:
		print('-1')
		break
else:
	fill = []
	for i in range(1, n + 1):
		if i not in mark:
			fill.append(i)
	c = 0
	for i in range(n):
		if c >= n:
			print('-1')
			break
		if a[i] == -1:
			a[i] = fill[c]
			c += 1
	print(*a)


f = lambda : map(int, input().split())
(n, m) = f()
p = list(f())
t = [0] * n
for (x, y) in zip(p, p[1:]):
	q = (y - x) % n
	if q == 0:
		q = n
	if 0 < t[x - 1] != q:
		print(-1)
		exit()
	t[x - 1] = q
p = set(t)
p.discard(0)
if len(p) + t.count(0) < n:
	print(-1)
	exit()
s = set(range(1, n + 1)).difference(p)
for q in t:
	print(q if q else s.pop())


inp = input().split()
n = int(inp[0])
m = int(inp[1])
leds = [int(x) for x in input().split()]
ans = [-1 for x in range(n)]
vals = [False for x in range(n)]
ok = True
for (led, nxt) in zip(leds, leds[1:]):
	val = (nxt - led) % n
	if val == 0:
		val = n
	old = ans[led - 1]
	if old == -1:
		if vals[val - 1]:
			ok = False
			break
		ans[led - 1] = val
		vals[val - 1] = True
	elif old != val:
		ok = False
		break
else:
	rest = [x for x in range(1, n + 1) if not vals[x - 1]]
	keys = [x for x in range(1, n + 1) if ans[x - 1] == -1]
	for (k, r) in zip(keys, rest):
		ans[k - 1] = r
if not ok:
	print(-1)
else:
	for (k, v) in enumerate(ans):
		print(v, end=' ')
	print('')