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

内存限制:512 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

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