C. Dreamoon Likes Coloring

链接：https://codeforces.ml/contest/1330/problem/C

Dreamoon likes coloring cells very much.

There is a row of nn cells. Initially, all cells are empty (don't contain any color). Cells are numbered from 11 to nn.

You are given an integer mm and mm integers l1,l2,…,lml1,l2,…,lm (1≤li≤n1≤li≤n)

Dreamoon will perform mm operations.

In ii-th operation, Dreamoon will choose a number pipi from range [1,n−li+1][1,n−li+1] (inclusive) and will paint all cells from pipi to pi+li−1pi+li−1 (inclusive) in ii-th color. Note that cells may be colored more one than once, in this case, cell will have the color from the latest operation.

Dreamoon hopes that after these mm operations, all colors will appear at least once and all cells will be colored. Please help Dreamoon to choose pipi in each operation to satisfy all constraints.

Input

The first line contains two integers n,mn,m (1≤m≤n≤1000001≤m≤n≤100000).

The second line contains mm integers l1,l2,…,lml1,l2,…,lm (1≤li≤n1≤li≤n).

Output

If it's impossible to perform mm operations to satisfy all constraints, print "'-1" (without quotes).

Otherwise, print mm integers p1,p2,…,pmp1,p2,…,pm (1≤pi≤n−li+11≤pi≤n−li+1), after these mm operations, all colors should appear at least once and all cells should be colored.

If there are several possible solutions, you can print any.

Examples

input

Copy

5 3
3 2 2

output

Copy

2 4 1

input

Copy

10 1
1

output

Copy

-1

代码：

#include<bits/stdc++.h>
using namespace std;
long long n,h,t,k,x,m,s,min1,max1,ans;
long long a[200001];
long long l[200001],r[200001];
int main()
{
	cin>>n>>m;
	s=0;
	for(int i=1;i<=m;i++)
	{
		cin>>a[i];
		s+=a[i];
	}
	
	int j=1;
	if(s<n||m>n)
	{
		cout<<-1;
		return 0;
	}
	s-=n;
	int flag=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i]+j-1>n)
		{
			flag=1;
			break;
		}
		if(s>=a[i]-1)
		{
			l[i]=j;
			s-=a[i]-1;
			j++;
		}
		else
		{
			l[i]=j;
			j=j+a[i]-s;
			s=0;
		}
	}
	if(flag==1)
	{
		cout<<-1;
		return 0;
	}
	for(int i=1;i<=m;i++)
	cout<<l[i]<<' ';
}