配点 : $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$ を加える。
• $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$ 行で出力してください。

4 6
1 1 4 4 2 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)$ です。

4 6
2 2 2 2 2 2

6 1 6 6

4 6
1 1 2 2 3 3

-1