Gem Sealing for Maximum Lexicographical Order

During an expedition, the brave hero XiaoLan discovered \( n \) mysterious gems whose magical energies are \( a_1,a_2,\cdots,a_n \). XiaoLan has \( n \) special magic boxes to seal these gems so that their power will not be misused. However, sealing a gem consumes XiaoLan's energy. Specifically, placing the \( i\)-th gem into the \( j\)-th box (which is only allowed if \( j\le i \)) consumes \( i-j \) energy.

Each box can hold at most one gem and each gem can be placed in at most one box. In addition, to avoid magical interference, any two adjacent boxes that are used (i.e. are not empty) must not contain gems with the same magical energy. (Note that two adjacent boxes may both be left empty.)

XiaoLan starts with an energy level of \( k \). Without exceeding the energy limit, XiaoLan wishes to choose a way to place the gems so that the sequence of magical energy values recorded in the boxes is lexicographically maximum. In the sequence, an empty box is recorded as \( -1 \).

Lexicographical Order: Given two sequences \( a \) and \( b \) of the same length \( L \), if there is an index \( i \) such that \( a_j = b_j \) for all \( 1\le j < i \) but \( a_i b_i \), then \( a \) is lexicographically larger. If no such \( i \) exists, the sequences are equal in lexicographical order.

Your task is to help XiaoLan determine the placement of gems into boxes that yields the lexicographically maximum sequence without exceeding the energy limit \( k \).

inputFormat

The first line contains two integers \( n \) and \( k \) (the number of gems/boxes and the available energy, respectively). The second line contains \( n \) integers \( a_1,a_2,\dots,a_n \), representing the magical energy value of each gem.

You may assume that the input satisfies \( 1 \le n \le 10^3 \) and \( 0 \le k \le 10^9 \). (Additional constraints may apply.)

outputFormat

Output a single line containing \( n \) integers. The \( j\)-th integer represents the magical energy of the gem placed in box \( j \), or \( -1 \) if the box is left empty. The output sequence should be lexicographically maximum among all valid placements that do not exceed the energy limit.

sample

3 2
1 2 3

3 2 -1