Problem: n children are standing in a circle and playing a game. Children's numbers in clockwise order form a permutation a1, a2, ..., an 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 ai 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 l1, l2, ..., lm — indices of leaders in the beginning of each step. Child with number l1 is the first leader in the game. 

Write a program which will restore a possible permutation a1, a2, ..., an. 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 l1, l2, ..., lm (1 ≤ li ≤ n) — indices of leaders in the beginning of each step.

Output

Print such permutation of n numbers a1, a2, ..., an that leaders in the game will be exactly l1, l2, ..., lm 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 + a2 = 3. 
  * Leadership goes from 3 to 3 + a3 = 5. As it's greater than 4, it's going in a circle to 1. 
  * Leadership goes from 1 to 1 + a1 = 4. 
  * Leadership goes from 4 to 4 + a4 = 8. Thus in circle it still remains at 4. 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

public class Main {

	class IOManager {
		BufferedReader reader;
		PrintWriter writer;
		StringTokenizer tokenizer;

		IOManager() {
			reader = new BufferedReader(new InputStreamReader(System.in));
			writer = new PrintWriter(new BufferedOutputStream(System.out));
		}

		IOManager(String file) throws FileNotFoundException {
			reader = new BufferedReader(new FileReader(file));
			writer = new PrintWriter(new BufferedOutputStream(System.out));
		}

		String next() throws IOException {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				String line = reader.readLine();
				if (line == null)
					throw new IOException("No lines left.");
				tokenizer = new StringTokenizer(line);
			}
			return tokenizer.nextToken();
		}

		public Integer nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public Long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public Double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public void writeSpace(Object obj) {
			writer.print(obj.toString() + " ");
		}

		public void writeLine(Object obj) {
			writer.println(obj.toString());
		}

		public void writeDouble(Double x, int n) {
			String format = "%." + n + "f";
			writer.printf(format, x);
		}

		public void write(Object obj) {
			writer.print(obj.toString());
		}

		public void close() {
			writer.close();
		}
	}

	class Pair<T extends Comparable> implements Comparable {
		public T u, v;

		public Pair(T u, T v) {
			this.u = u;
			this.v = v;
		}

		@Override
		public int compareTo(Object o) {
			Pair that = (Pair) o;
			if (u.compareTo(that.u) != 0)
				return u.compareTo(that.u);
			return v.compareTo(that.v);
		}
	}

	class Graph {
		public int n, m;
		public List<Integer>[] adj;

		public Graph(int n, int m) {
			this.n = n;
			this.m = m;
			adj = new List[n + 1];
			for (int i = 0; i <= n; ++i) {
				adj[i] = new ArrayList<>();
			}
		}

		public void add(int u, int v) {
			adj[u].add(v);
		}

		public void add2Ways(int u, int v) {
			add(u, v);
			add(v, u);
		}

		public void dfs(int i, boolean fr[]) {
			fr[i] = false;
			for (int j : adj[i]) {
				if (fr[j]) {
					dfs(j, fr);
				}
			}
		}

		public boolean isConnected() {
			boolean fr[] = new boolean[n + 1];
			Arrays.fill(fr, true);
			dfs(1, fr);
			for (int i = 2; i <= n; ++i) {
				if (fr[i])
					return false;
			}
			return true;
		}

		public boolean hasEuclideanPath() {
			if (!isConnected())
				return false;
			int cnt = 0;
			for (int i = 1; i <= n; ++i) {
				if (adj[i].size() % 2 == 1)
					cnt++;
			}
			return cnt <= 2;
		}

		public boolean dfsHamiltonian(int i, boolean[] fr, int reached) {
			fr[i] = false;
			reached++;
			if (reached == n)
				return true;
			for (int j : adj[i]) {
				if (fr[j]) {
					if (dfsHamiltonian(j, fr, reached))
						return true;
				}
			}
			fr[i] = true;
			return false;
		}

		public boolean hasHamiltonianPathFrom(int st) {
			boolean fr[] = new boolean[n + 1];
			Arrays.fill(fr, true);
			return dfsHamiltonian(st, fr, 0);
		}
	}

	// Actually rooted forest
	class Tree extends Graph {

		public Tree(int n, int m) {
			super(n, m);
		}

		public int getHeight(int i) {
			int res = 0;
			for (Integer j : adj[i]) {
				res = Math.max(res, getHeight(j) + 1);
			}
			return res;
		}
	}

	class FenwickTree {
		int n;
		int tree[];

		public FenwickTree() {

		}

		public FenwickTree(int maxn) {
			n = maxn;
			tree = new int[maxn + 10];
		}

		public void add(int i, int x) {
			while (i <= n) {
				tree[i] += x;
				i += i & (-i);
			}
		}

		public void add(int i) {
			add(i, 1);
		}

		public int get(int i) {
			int res = 0;
			while (i > 0) {
				res += tree[i];
				i -= i & (-i);
			}
			return res;
		}
	}

	class DoubleMatrix {

		public int m, n;
		public double a[][];

		public DoubleMatrix(int _m, int _n) {
			m = _m;
			n = _n;
			a = new double[m][n];
		}

		public DoubleMatrix(double x[][]) {
			if (x.length == 0)
				return;
			m = x.length;
			n = x[0].length;
			a = new double[m][n];
			for (int i = 0; i < m; ++i) {
				for (int j = 0; j < n; ++j) {
					a[i][j] = x[i][j];
				}
			}
		}

		public DoubleMatrix invert() {
			if (m != n)
				return null;
			double x[][] = new double[n][n];
			double b[][] = new double[n][n];
			int index[] = new int[n];
			for (int i = 0; i < n; ++i)
				b[i][i] = 1;

			// Transform the matrix into an upper triangle
			DoubleMatrix a2 = new DoubleMatrix(a);
			a2.gaussian(index);

			// Update the matrix b[i][j] with the ratios stored
			for (int i = 0; i < n - 1; ++i)
				for (int j = i + 1; j < n; ++j)
					for (int k = 0; k < n; ++k)
						b[index[j]][k] -= a2.a[index[j]][i] * b[index[i]][k];

			// Perform backward substitutions
			for (int i = 0; i < n; ++i) {
				x[n - 1][i] = b[index[n - 1]][i] / a2.a[index[n - 1]][n - 1];
				for (int j = n - 2; j >= 0; --j) {
					x[j][i] = b[index[j]][i];
					for (int k = j + 1; k < n; ++k) {
						x[j][i] -= a2.a[index[j]][k] * x[k][i];
					}
					x[j][i] /= a2.a[index[j]][j];
				}
			}
			return new DoubleMatrix(x);
		}

		// Method to carry out the partial-pivoting Gaussian
		// elimination.  Here index[] stores pivoting order.

		public void gaussian(int index[]) {
			int n = index.length;
			double c[] = new double[n];

			// Initialize the index
			for (int i = 0; i < n; ++i)
				index[i] = i;

			// Find the rescaling factors, one from each row
			for (int i = 0; i < n; ++i) {
				double c1 = 0;
				for (int j = 0; j < n; ++j) {
					double c0 = Math.abs(a[i][j]);
					if (c0 > c1) c1 = c0;
				}
				c[i] = c1;
			}

			// Search the pivoting element from each column
			int k = 0;
			for (int j = 0; j < n - 1; ++j) {
				double pi1 = 0;
				for (int i = j; i < n; ++i) {
					double pi0 = Math.abs(a[index[i]][j]);
					pi0 /= c[index[i]];
					if (pi0 > pi1) {
						pi1 = pi0;
						k = i;
					}
				}

				// Interchange rows according to the pivoting order
				int itmp = index[j];
				index[j] = index[k];
				index[k] = itmp;
				for (int i = j + 1; i < n; ++i) {
					double pj = a[index[i]][j] / a[index[j]][j];

					// Record pivoting ratios below the diagonal
					a[index[i]][j] = pj;

					// Modify other elements accordingly
					for (int l = j + 1; l < n; ++l)
						a[index[i]][l] -= pj * a[index[j]][l];
				}
			}
		}

		public DoubleMatrix mul(DoubleMatrix b) {
			if (n != b.m)
				return null;
			DoubleMatrix c = new DoubleMatrix(m, b.n);
			for (int i = 0; i < m; ++i) {
				for (int j = 0; j < b.n; ++j) {
					c.a[i][j] = 0;
					for (int k = 0; k < n; ++k) {
						c.a[i][j] += a[i][k] * b.a[k][j];
					}
				}
			}
			return c;
		}

		public String toString() {
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < m; ++i) {
				for (int j = 0; j < n; ++j) {
					sb.append(a[i][j]);
					sb.append(j == n - 1 ? "\n" : " ");
				}
			}
			return sb.toString();
		}

		public DoubleMatrix transpose() {
			DoubleMatrix res = new DoubleMatrix(n, m);
			for (int i = 0; i < n; ++i) {
				for (int j = 0; j < m; ++j) {
					res.a[i][j] = a[j][i];
				}
			}
			return res;
		}
	}

	IOManager ioManager;

	Main() {
		ioManager = new IOManager();
	}

	Main(String file) throws FileNotFoundException {
		ioManager = new IOManager(file);
	}

	int n, m;
	int a[];
	boolean fr[];
	int res[];

	void solve() throws IOException {
		n = ioManager.nextInt();
		m = ioManager.nextInt();
		a = new int[m + 1];
		fr = new boolean[n + 1];
		res = new int[n + 1];
		for (int i = 1; i <= m; ++i) {
			a[i] = ioManager.nextInt();
		}
		Arrays.fill(fr, true);
		Arrays.fill(res, -1);
		for (int i = 1; i < m; ++i) {
			int d = a[i + 1] > a[i] ? a[i + 1] - a[i] : a[i + 1] + n - a[i];
			if (res[a[i]] == d)
				continue;
			if (res[a[i]] == -1 && fr[d]) {
				res[a[i]] = d;
				fr[d] = false;
			} else {
				ioManager.writeLine(-1);
				return;
			}
		}
		for (int i = 1; i <= n; ++i) {
			if (res[i] == -1) {
				for (int j = 1; j <= n; ++j) {
					if (fr[j]) {
						res[i] = j;
						fr[j] = false;
						break;
					}
				}
			}
		}
		for (int i = 1; i <= n; ++i) {
			ioManager.writeSpace(res[i]);
		}
	}

	void close() {
		ioManager.close();
	}

	public static void main(String args[]) throws IOException {
		Main solver;
//		solver = new Main();
        if (!"true".equals(System.getProperty("ONLINE_JUDGE"))) {
            solver = new Main("input.txt");
        } else {
            solver = new Main();
        }
		solver.solve();
		solver.close();
	}
}