题目描述

考虑对一个包含 $N$ 个正整数的序列 $A = (A_1, A_2, \ldots, A_N)$ 执行下面的操作，得到一个序列 $I = (i_1, i_2, \ldots, i_K)$。

• 对于每个 $k = 1, 2, \ldots, K$，按顺序执行以下步骤：
  • 选择一个 $i$，使得 $A_i = \\min\\{A_1, A_2, \ldots, A_N\\}$。
  • 令 $i_k = i$。
  • 将 $A_i$ 增加 $1$。

给定整数 $N$、$K$ 和序列 $I$，判断是否存在一个正整数序列 $A$，使得通过操作得到序列 $I$。如果存在，找出字典序最小的满足条件的序列。

约束条件

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

输入

输入以以下格式从标准输入给出：

$N$ $K$

$i_1$ $i_2$ $\ldots$ $i_K$

输出

如果不存在一个满足条件的正整数序列 $A$，则输出 -1。如果存在，输出满足条件的序列 $A$ 中字典序最小的序列，一行中用空格间隔。

示例输入1

4 6
1 1 4 4 2 1

示例输出1

1 3 3 2

可以通过操作得到序列 $I = (1, 1, 4, 4, 2, 1)$ 的一些满足条件的序列为 $(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