Bajtazar 是 Bajtlandia 国家铁路公司（BKP）的一名列车员，该公司以拥有整个 Bajtlandia 最长的客运列车而闻名。特殊的列车需要特殊的解决方案，因此 BKP 的管理层制定了旨在提高列车员工作效率的规定。其中规定，验票过程按如下方式进行：

• 开始时，列车中的所有 $n$ 个车厢按编号从 1 到 $n$ 编号。同样地，每位 $k$ 名列车员也获得一个唯一的标识符，是从 1 到 $k$ 范围内的一个整数。
• 然后，每位列车员从编号等于其标识符的车厢开始验票。
• 列车员在完成自己当前车厢的验票后，将开始验票尚未检查过的车厢中编号最小的一个。如果有两位列车员在同一时刻完成了验票，则编号较小的列车员拥有优先权。
• 如果一位列车员完成当前车厢的验票后，已没有更多的车厢需要验票，则该列车员的工作就结束了。
• 当所有车厢的车票都已检查完毕时，列车的验票工作就结束了。

出于经济原因，列车员的数量永远不会超过列车中的车厢数量。

BKP 的所有车厢都是相同的，因此验票所需的时间仅取决于列车员的敏捷程度。此外，BKP 十分重视员工的独特性，因此不会有两位列车员验票所需时间相同。

在列车验票结束后，Bajtazar 的同事们总喜欢炫耀谁最后检查的车厢编号更大。请帮助 Bajtazar 判断他是否也有可以炫耀的资本，编写一个程序，确定每位列车员最后检查的车厢编号。

输入格式

输入的第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 2 \cdot 10^{13}$，$1 \le k \le 100,000$，且 $k \le n$），分别表示车厢的数量和列车员的数量。

第二行包含 $k$ 个互不相同的整数 $a_1, ..., a_k$。其中，$a_i$（$1 \le a_i \le 10^5$）表示标识符为 $i$ 的列车员检查一个车厢所需的时间。

输出格式

输出的第一行应包含 $k$ 个整数，按标识符升序排列，表示每位列车员最后检查的车厢编号。

示例

输入

10 3
3 5 6

输出

10 9 7

说明

上图展示了验票过程的进展。列表示时间单位的推进，行表示不同的列车员，加粗的数字表示列车员在相应时间所处的车厢编号。