I - Candies Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

N 人のこどもが一列に並んでいます。最初、前から i 番目のこどもは A_i 個のアメを持っています。

あなたは以下の操作を M 回続けて行います。

  • 持っているアメの個数が最も少ないこども(複数いるならそのうち最も前にいるこども) 1 人に、アメを K 個与える

M 回の操作が終了したときに、それぞれのこどもが持っているアメの個数を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^{12}
  • 1 \leq K \leq 10^5
  • 0 \leq A_i \leq 10^{12}
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M K
A_1 A_2 \ldots A_N

出力

M 回の操作が終了したときに、前から i 番目のこどもが持っているアメの個数を B_i として、B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。

入力例 1

4 3 2
3 4 1 10

出力例 1

5 4 5 10
  • 1 回目の操作では、前から 3 番目のこどもにアメを与えます。それぞれのこどもが持っているアメの個数は 3,4,3,10 になります。
  • 2 回目の操作では、前から 1 番目のこどもにアメを与えます。それぞれのこどもが持っているアメの個数は 5,4,3,10 になります。
  • 3 回目の操作では、前から 3 番目のこどもにアメを与えます。それぞれのこどもが持っているアメの個数は 5,4,5,10 になります。

入力例 2

2 1000000000000 100000
1000000000000 1

出力例 2

50000500000000000 50000500000000001

入力例 3

3 1415 9
26 53 58

出力例 3

4292 4292 4288

Problem Statement

N children are standing in line. Initially, the i-th child from the front has A_i candies.

You are going to repeat the following operation M times.

  • Give K candies to the child with the fewest candies (if there are multiple such children, to the frontmost one among them).

Find how many candies the children will have after the M operations.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^{12}
  • 1 \leq K \leq 10^5
  • 0 \leq A_i \leq 10^{12}
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M K
A_1 A_2 \ldots A_N

Output

Let B_i be the number of candies that the i-th child from the front will have after the M operations. Print B_1,B_2,\ldots, and B_N in this order, with spaces in between.

Sample Input 1

4 3 2
3 4 1 10

Sample Output 1

5 4 5 10
  • The 1-st operation gives candies to the 3-rd child from the front. Now, the children have 3,4,3, and 10 candies.
  • The 2-nd operation gives candies to the 1-st child from the front. Now, the children have 5,4,3, and 10 candies.
  • The 3-rd operation gives candies to the 3-rd child from the front. Now, the children have 5,4,5, and 10 candies.

Sample Input 2

2 1000000000000 100000
1000000000000 1

Sample Output 2

50000500000000000 50000500000000001

Sample Input 3

3 1415 9
26 53 58

Sample Output 3

4292 4292 4288