众所周知，fpdqwq同学会很多算法，尤其擅长排序。但这题不仅和排序没有任何关系，甚至和fpdqwq也没有关系。

这次我们的主人公是小明同学。一天，小明打算去买酒喝，他家里有$n$个瓶子，然而瓶子太多了，他只打算带$k$个瓶子去集市上。

小明将$k$个瓶子交给商人之后，商人用它们装一些酒给小明。所有的瓶子都没有刻度，只在瓶口标注了容量，第$i$个瓶子的容量为$V_i$。商人比较吝啬，他们并不会把所有的瓶子都装满酒。他们拿到瓶子后，会跑到酒桶附近鼓捣一通，弄出一小点酒来交差。小明当然知道他们会来这一手，于是事先了解了商人鼓捣的具体内容。

商人在酒桶边只会做如下的3种操作：

1.将某个瓶子装满酒；

2.将某个瓶子中的酒全部倒回酒桶；

3.将酒从瓶子$a$倒向瓶子$b$，直到瓶子$b$满或者瓶子$a$空。倾倒过程中的损耗可以忽略。

商人拿出的酒，当然是这些操作能得到的最小正体积。小明知道，对于不同的瓶子组合，商人可能会被迫给出不同体积的酒。小明希望找到最优的瓶子组合，使得商人给出尽量多的酒。

由于小明想在携带的瓶子个数和获得的酒量之间做权衡（？？？），所以请对所有的$k$($1\leq k \leq n$)输出答案

输入格式

第一行两个整数$n,maxv$，表示瓶子个数和瓶子最大容量

接下来一行$n$个整数，用空格分隔，分别表示每个瓶子的容量$V_i$

输出格式

一行$n$个整数，用空格分隔，第$i$个数代表$k=i$时的答案

样例一

input

3 4
3 4 4

output

4 4 1 

样例解释

$k=1$时，只需要随便取一个最大的瓶子，商人无论怎么捣腾都无法给小明小于4体积的酒。

$k=2$时，只需要取两个最大的瓶子，商人无论怎么捣腾都无法给小明小于4体积的酒。

$k=3$时，必须把所有瓶子都带上。

商人可以对容量为4的瓶子执行操作1，再对这个瓶子和容量为3的瓶子执行操作3，再对容量为3的瓶子执行操作2，即可获得1体积的酒。

样例二

input

1 1000000
1000000

output

1000000 

样例解释

$k=1$时，商人无论怎么捣腾都无法给小明小于1000000体积的酒。

数据范围与约定

子任务1 (13 pts): $1\leq n \leq 10$

子任务2 (34 pts): $1\leq n \leq 5000$

子任务3 (53 pts): 无额外限制

对于全部数据：$1 \leq n,maxv \leq 1000000$，$1 \leq V_i \leq maxv$。

时间限制：$1\texttt{s}$

空间限制：$256\texttt{MB}$

提示

1.读入量较大，请注意读入效率

2.佛曰：皤佛佛怯曳罰是冥伽豆梵瑟呐參顛呐摩呐無怯羅訶隸提菩