405679: GYM102035 C Apple Shops

Ayoub wants to buy k boxes of apples, and there are n shops where he can buy apples from. The price of one box of apples in the i_th shop equals to p_i.

It is obvious that Ayoub should go to the shop with the minimal price per box. When the government saw everyone buying from the same shop, they made a special rule so that people will buy from different shops.

The cost of buying the j_th apple box from the i_th shop is equal to p_i + (j - 1)  ×  x

For example, if the price of one box from a specific shop is 5 and x = 3. If you want to buy 3 boxes, you will pay 5 money on the first box and 5 + x on the second box, and 5 + 2 × x on the third box, in total paying 5 + 8 + 11 = 24.

Now you should tell Ayoub how many boxes he should buy from every shop so that the total money he will pay is minimized.

First line contains 3 integers n k x (1 ≤ n ≤ 10⁵) (1 ≤ k, x ≤ 10⁹) which are the number of shops and the number of box Ayoub wants to buy and the amount of money you should pay more after buying a box from a specific shop.

Second line contains n integers, the i_th one is p_i (1 ≤ p_i ≤ 10⁹) which is the price of a box of apples from the i_th shop.

You should print n integers, the i_th one should be the number of box Ayoub should buy from the i_th shop.

Make sure that the amount of money will be payed will be minimized as possible.

If there are more than one answer you can print any of them.

3 2 5
2 2 2

1 1 0

4 4 3
1 5 2 3

2 0 1 1

In the second sample Ayoub will pay 1 and 4 to the first shop and will pay 2 to the third shop and will pay 3 to the fourth shop, in total he will buy 10 money.