题目描述

你是港区的一位指挥官，你可以通过培养指挥喵来增强舰队的实力，指挥喵由对应的喵箱培育。喵箱有 $k$ 个等级，等级越高稀有度越高。你每天会获得若干个喵箱（至少一个），然后再使用 ''一键放入'' 将这些喵箱放到喵窝里进行培育。''一键放入'' 会优先放入稀有度更高的喵箱（即按照稀有度从高到低排序后依次放入），放入的喵箱会排在已放入喵箱的后面，在每天结束时系统会自动扣除与喵窝中喵箱数量相等的钱。最开始时你的喵窝里没有喵箱。

因为你非常懒，所以你会等 $n$ 天后才把喵箱一起打开。在你 $n$ 天后进入喵窝时，你看到了 $m$ 个喵箱，用一个长度为 $m$ 的序列 $a$ 表示喵窝里按放入先后顺序排列的喵箱的等级。但是你已经忘了这 $n$ 天里你每天获得了多少喵箱了，你甚至忘了 $n$ 的值是多少，显然这有许多情况。你想知道，对于满足 $1 \leq n \leq m$ 的所有整数 $n$，在所有情况中，这 $n$ 天总共扣除的钱数至少为多少？

输入格式

第一行包含两个整数 $m\ (1 \leq m \leq 10^6)$，$k\ (1 \leq k \leq 10^6)$，分别表示喵窝中喵箱的数量和喵箱的最高等级。

第二行包含 $m$ 个整数 $a_{1}, a_{2}, \ldots, a_{m}\ (1 \leq a_i \leq k)$，表示喵窝中排列着的喵箱的等级。

输出格式

输出一行用空格间隔的 $m$ 个整数，其中第 $i$ 个整数表示当 $n=i$ 时在所有可能的情况下至少会扣除的钱数。如果没有合法的情况，请输出 $-1$。

3 3
2 3 1

-1 4 6 

8 4
3 2 4 2 1 2 3 2

-1 -1 -1 21 22 25 29 36 

提示

样例一解释：

当 $n=1$ 时，无法在一天内获得这 $3$ 个喵箱（第二个喵箱的等级大于第一个喵箱的等级，不符合 ``一键放入'' 从高到低放入的原则），因此输出 $-1$。

当 $n=2$ 时，第一天获得第一个喵箱，此时喵窝内有 $1$ 个喵箱，当天花费为 $1$；第二天获得后两个喵箱，此时喵窝内有 $3$ 个喵箱，当天花费为 $3$。因此总钱数为 $4$。

当 $n=3$ 时，每天依次获得一个喵箱，总钱数为 $1+2+3=6$。