题目描述

高桥王国有 $N$ 个居民。每个居民都有一个国民身份证号码；第 $i$ 个居民的身份证号是 $a_i$。在这里，所有的 $a_i$ 互不相同。

高桥有 $K$ 快糖果。他决定按照以下方式将这些糖果分发给居民，直到他没有多余的糖果为止。

• 当他有至少 $N$ 个糖果时，给每个居民分发一块糖果。
• 否则，令 $K'$ 是他当前拥有的糖果数目，并把每个具有最小 $K'$ 个身份证号码的居民分发一块糖果。

当所有的糖果都发完后，第 $i$ 个居民将会拥有多少块糖果？

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq 10^{18}$
• $1 \leq a_i \leq 10^9$
• 所有的 $a_i$ 互不相同。
• 输入中的所有值都是整数。

输入

输入的格式如下所示，从标准输入中获得：

$N$ $K$ $a_1$ $a_2$ $\ldots$ $a_N$

输出

打印 $N$ 行。第 $i$ 行应该包含第 $i$ 个居民收到的糖果数目。

示例输入 1

2 7
1 8

示例输出 1

4
3

高桥将按以下方式分发糖果。

• 每个人都分发一块，剩下 $5$ 块。
• 每个人都分发一块，剩下 $3$ 块。
• 每个人都分发一块，剩下 $1$ 块。
• 给第 $1$ 个居民一块，剩下没有糖果。

最后，第 $1$ 个居民将收到 $4$ 块糖果，第 $2$ 个居民将收到 $3$ 块糖果。

示例输入 2

1 3
33

示例输出 2

3

由于只有一个居民，高桥将把所有糖果都分发给这个第 $1$ 个居民。

示例输入 3

7 1000000000000
99 8 2 4 43 5 3

示例输出 3

142857142857
142857142857
142857142858
142857142857
142857142857
142857142857
142857142857