「2017 山东二轮集训 Day3」第一题

传统 10000 ms 512 MiB

$64$ 通过 $137$ 提交

题目描述

小火车的 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$。

样例

输入

5
100
1
1
2
2
3

输出

100
100
99
99
98

数据范围与提示

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

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