/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 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 人目の国民がもらったお菓子の個数を出力せよ。
入力例 1
2 7 1 8
出力例 1
4 3
高橋君はお菓子を次の手順で配ります。
- 全員に 1 個ずつお菓子を配り、高橋君の持っているお菓子は 5 個になる。
- 全員に 1 個ずつお菓子を配り、高橋君の持っているお菓子は 3 個になる。
- 全員に 1 個ずつお菓子を配り、高橋君の持っているお菓子は 1 個になる。
- 1 人目の国民に 1 個お菓子を配り、高橋君の持っているお菓子は無くなる。
最終的に 1 人目の国民は 4 個、2 人目の国民は 3 個のお菓子を手に入れることができます。
入力例 2
1 3 33
出力例 2
3
国民が 1 人しかいないので、高橋君は全てのお菓子を 1 人目の国民に配ることになります。
入力例 3
7 1000000000000 99 8 2 4 43 5 3
出力例 3
142857142857 142857142857 142857142858 142857142857 142857142857 142857142857 142857142857
Score : 300 points
Problem Statement
There are N citizens in the Kingdom of Takahashi. Each citizen has a national ID number; the ID of the i-th citizen is a_i. Here, all a_i are pairwise different.
Takahashi has K pieces of sweets. He has decided to hand out these pieces to the citizens in the following way until he has no more pieces.
- When he has N or more pieces, hand out one piece to every citizen.
- Otherwise, let K' be the number of pieces he has at the moment, and hand out one piece to each of the citizens with the K' smallest IDs.
When all pieces are handed out, how many pieces will the i-th citizen have?
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{18}
- 1 \leq a_i \leq 10^9
- All a_i are pairwise different.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K a_1 a_2 \ldots a_N
Output
Print N lines. The i-th line should contain the number of pieces of sweets received by the i-th citizen.
Sample Input 1
2 7 1 8
Sample Output 1
4 3
Takahashi will hand out the pieces as follows.
- Hand out one piece to everyone, leaving Takhashi with 5 pieces.
- Hand out one piece to everyone, leaving Takhashi with 3 pieces.
- Hand out one piece to everyone, leaving Takhashi with 1 piece.
- Hand out one piece to the 1-st citizen, leaving Takhashi with no pieces.
In the end, the 1-st citizen will receive 4 pieces, and the 2-nd citizen will receive 3 pieces.
Sample Input 2
1 3 33
Sample Output 2
3
Since there is just one citizen, Takahashi will hand out all pieces to that 1-st citizen.
Sample Input 3
7 1000000000000 99 8 2 4 43 5 3
Sample Output 3
142857142857 142857142857 142857142858 142857142857 142857142857 142857142857 142857142857