题目描述

小火车的 ddl 赶不完了，他不愿意也没时间去思考题目背景到底应该怎么写了。

$ n $ 个人要赶 $ k $ 个 ddl，第 $ n $ 个人会提出一个 ddl 划分方案（也就是每个人分到多少个 ddl，总和为 $ k $，当然每个人分到的都是整数），然后进行投票，如果有超过 $ v_n $ 的人同意则通过，否则他会被踢掉，剩下的人会继续分 ddl。

人们都是很勤奋的，所以他们会这样行动：

1. 保证自己不被踢掉。
2. 在条件 1 相同时，能分到尽量多的 ddl。
3. 在条件 1、2 相同时，能踢掉尽量多的人。
4. 都相同就随意操作。

现在告诉你 $ n, k $ 和 $ v_i $，问前 $ i $ 个人分 ddl 的时候最后一个人能分到多少，或者他一定会被扔到海里。

输入格式

第一行一个整数 $ n $，表示人数。
第二行一个整数 $ k $，表示 ddl 数。
接下来 $ n $ 行每行一个整数，第 $ i $ 行表示 $ v_i $。

输出格式

$ n $ 行每行一个整数，第 $ i $ 行表示前 $ i $ 个人分 ddl 的时候最后一个人能分到多少，如果他一定会被踢掉则输出 $ -1 $。

样例

input

5
100
1
1
2
2
3

output

100
100
99
99
98

数据范围与提示

对于 $ 20\% $ 的数据 $ n \leq 2000 $；
对于另外 $ 20\% $ 的数据 $ k = 10 ^ {18} $；
对于 $ 100\% $ 的数据 $ n \leq 1000000, k \leq 10 ^ {18} $。

数据量非常大请使用尽量快的输入输出方式。