Minimize the Difference

Time limit1sMemory limit128 MB

Summary

Given an array with a budget of T total decrements (each element bounded below by 1), reduce elements to minimize the maximum adjacent absolute difference and output the resulting array.

Level: Medium7 of 10
Topics: Binary search, Greedy, Array
Solved: No attempts yet

Problem

You are given an array A of N integers. In one operation, you may choose one element of the array and decrease its value by 1. No element may become smaller than 1.

You may perform at most T operations. Change the array so that the maximum absolute difference between two adjacent elements is as small as possible, then print the changed array.

Input

The first line contains N and T. (2 <= N <= 100000, 1 <= T <= 10^9)

The second line contains the elements A1, A2, ..., AN of the array, separated by spaces. (1 <= Ai < 10^9)

Output

Print the elements A1, A2, ..., AN of a changed array satisfying the conditions, separated by spaces.

Each printed element must not exceed its original value, and the total number of decreases must not exceed T. You do not have to use all operations.

Examples3

Example 1
Input
```
5 2
3 2 3 2 2
```
Expected output
```
2 2 2 2 2
```
Example 2
Input
```
5 5
4 2 3 7 6
```
Expected output
```
3 2 3 4 5
```
Example 3
Input
```
3 6
10 10 1
```
Expected output
```
9 5 1
```