Concert Rest Scheduling

During a concert, a band comprising (n) musicians performs continuously for (t) minutes. Each musician (i) wishes to take a break for (a_i) minutes. The break for musician (i) will occur in the interval ([s_i, s_i+a_i)), where (s_i) is the start time of their break. To maintain overall harmony, it is required that at no moment in time are three or more musicians resting simultaneously (note that one musician‘s break can start exactly at the moment another's break ends). Your task is to determine a valid schedule by assigning each musician a start time (s_i) such that all breaks occur within the (t) minutes of the performance and the overlap condition is satisfied.

inputFormat

The first line contains two integers (n) and (t) ((1 \le n \le 10^5), (1 \le t \le 10^9)) --- the number of musicians and the total performance time in minutes. The second line contains (n) integers (a_1, a_2, \dots, a_n), where (a_i) denotes the desired break duration (in minutes) for the (i)-th musician. It is guaranteed that there exists a valid schedule.

outputFormat

Output (n) integers (s_1, s_2, \dots, s_n) separated by spaces, where (s_i) is the start time for the (i)-th musician's break. This means musician (i) will rest during the interval ([s_i, s_i+a_i)). The schedule must meet the condition that at any time, fewer than three musicians are resting simultaneously.

sample

3 10
3 3 3

0 0 3