配点 : $300$ 点

問題文

高橋王国には $N$ 人の国民がいます。 全ての国民には国民番号が割り振られており、 $i$ 人目の国民の国民番号は $a_i$ です。ここで、$a_i$ は互いに異なります。

高橋君は $K$ 個のお菓子を持っています。高橋君は次のルールに従って、持っているお菓子が無くなるまで国民にお菓子を配ることにしました。

• 持っているお菓子が $N$ 個以上ある場合、全員に $1$ 個ずつお菓子を配る。
• そうでない場合、その時点で高橋くんが持っているお菓子の個数を $K'$ として、国民番号が小さい方から $K'$ 人に $1$ 個ずつ配る。より厳密には、$a_i$ の値が小さい方から $K'$ 人を選び、選んだ人に $1$ 個ずつお菓子を配る。

全てのお菓子を配り終えたとき、$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$ 人目の国民がもらったお菓子の個数を出力せよ。

2 7
1 8

4
3

高橋君はお菓子を次の手順で配ります。

• 全員に $1$ 個ずつお菓子を配り、高橋君の持っているお菓子は $5$ 個になる。
• 全員に $1$ 個ずつお菓子を配り、高橋君の持っているお菓子は $3$ 個になる。
• 全員に $1$ 個ずつお菓子を配り、高橋君の持っているお菓子は $1$ 個になる。
• $1$ 人目の国民に $1$ 個お菓子を配り、高橋君の持っているお菓子は無くなる。

最終的に $1$ 人目の国民は $4$ 個、$2$ 人目の国民は $3$ 個のお菓子を手に入れることができます。

1 3
33

3

国民が $1$ 人しかいないので、高橋君は全てのお菓子を $1$ 人目の国民に配ることになります。

7 1000000000000
99 8 2 4 43 5 3

142857142857
142857142857
142857142858
142857142857
142857142857
142857142857
142857142857