/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 800 点
問題文
N 項からなる正整数列 A = (A_1, A_2, \ldots, A_N) に対して、次の操作を行い、数列 I = (i_1, i_2, \ldots, i_K) を得ることを考えます。
- k = 1, 2, \ldots, K の順に、次を行う。
- A_i = \min\{A_1, A_2, \ldots, A_N\} となる i をひとつ選ぶ。
- i_k = i と定める。
- A_i に 1 を加える。
整数 N, K と数列 I が与えられます。
操作の結果として I を得ることが可能であるような正整数列 A が存在するかを判定してください。存在する場合には、そのようなもののうち辞書順最小のものを答えてください。
制約
- 1\leq N, K\leq 3\times 10^5
- 1\leq i_k\leq N
入力
入力は以下の形式で標準入力から与えられます。
N K i_1 i_2 \ldots i_K
出力
操作の結果として I を得ることが可能であるような正整数列 A が存在しない場合、-1 と出力してください。
存在する場合、そのような正整数列 A のうち、辞書順最小のものを、空白で区切って 1 行で出力してください。
入力例 1
4 6 1 1 4 4 2 1
出力例 1
1 3 3 2
操作の結果として I = (1,1,4,4,2,1) を得ることが可能な正整数列 A としては、(1, 3, 3, 2), (2, 4, 5, 3) などがあります。そのうち辞書順最小のものは (1, 3, 3, 2) です。
入力例 2
4 6 2 2 2 2 2 2
出力例 2
6 1 6 6
入力例 3
4 6 1 1 2 2 3 3
出力例 3
-1
Score : 800 points
Problem Statement
Consider doing the operation below on a sequence of N positive integers A = (A_1, A_2, \ldots, A_N) to obtain a sequence I = (i_1, i_2, \ldots, i_K).
- For each k = 1, 2, \ldots, K in this order, do the following.
- Choose an i such that A_i = \min\{A_1, A_2, \ldots, A_N\}.
- Let i_k = i.
- Add 1 to A_i.
You are given integers N, K, and a sequence I.
Determine whether there exists a sequence of positive integers A for which it is possible to obtain I from the operation. If it exists, find the lexicographically smallest such sequence.
Constraints
- 1\leq N, K\leq 3\times 10^5
- 1\leq i_k\leq N
Input
Input is given from Standard Input in the following format:
N K i_1 i_2 \ldots i_K
Output
If there is no sequence of positive integers A for which it is possible to obtain I from the operation, print -1.
If it exists, print the lexicographically smallest among such sequences A, in one line, with spaces in between.
Sample Input 1
4 6 1 1 4 4 2 1
Sample Output 1
1 3 3 2
Some of the sequences for which it is possible to obtain I = (1,1,4,4,2,1) from the operation are (1, 3, 3, 2) and (2, 4, 5, 3). The lexicographically smallest among them is (1, 3, 3, 2).
Sample Input 2
4 6 2 2 2 2 2 2
Sample Output 2
6 1 6 6
Sample Input 3
4 6 1 1 2 2 3 3
Sample Output 3
-1