题目描述

$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$ が存在するかを判定してください。存在する場合には、そのようなもののうち辞書順最小のものを答えてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $K$ $i_1$ $i_2$ $\ldots$ $i_K$

输出格式

操作の結果として $I$ を得ることが可能であるような正整数列 $A$ が存在しない場合、-1 と出力してください。 存在する場合、そのような正整数列 $A$ のうち、辞書順最小のものを、空白で区切って $1$ 行で出力してください。

4 6
1 1 4 4 2 1

1 3 3 2

4 6
2 2 2 2 2 2

6 1 6 6

4 6
1 1 2 2 3 3

-1

提示

制約

• $1\leq\ N,\ K\leq\ 3\times\ 10^5$
• $1\leq\ i_k\leq\ N$

Sample Explanation 1

操作の結果として $I\ =\ (1,1,4,4,2,1)$ を得ることが可能な正整数列 $A$ としては、$(1,\ 3,\ 3,\ 2)$, $(2,\ 4,\ 5,\ 3)$ などがあります。そのうち辞書順最小のものは $(1,\ 3,\ 3,\ 2)$ です。