Il re Primonida sta organizzando un torneo per trovare il gladiatore più forte di tutte le terre. In totale $N$ gladiatori si sono recati al Colosseo per riportare onore e gloria alle proprie città natali. Ogni gladiatore inizia con una certa quantità di vitalità. La vitalità è simile ai punti ferita in quanto riflette la quantità di danni che un gladiatore può subire, ma rappresenta anche la quantità di danni che può infliggere (poiché serve energia per sferrare colpi potenti).

Il torneo è composto da $K$ round. Ad ogni round, il re dispone i gladiatori in fila in ordine crescente di vitalità rimanente, risolvendo gli eventuali ex aequo in modo casuale. Il re Primonida crede che la vera forza di un gladiatore risieda nella sua capacità di incassare i colpi, quindi ordina al primo gladiatore (quello con la vitalità rimanente più bassa) di sferrare il suo colpo più forte al secondo gladiatore. Questo colpo sottrae la vitalità del primo gladiatore dalla vitalità del secondo gladiatore. Dopo che il secondo gladiatore ha subito il colpo, sferra il suo colpo più forte (usando la sua nuova vitalità ridotta) al terzo gladiatore, e così via. Questo processo si ripete finché il penultimo gladiatore non sferra il suo colpo più forte all'ultimo gladiatore (che non può attaccare nessuno).

Si noti che nel processo descritto sopra la vitalità di un gladiatore non può mai scendere sotto lo zero. (Un gladiatore con vitalità pari a zero sferra un colpo debole che non infligge alcun danno al gladiatore successivo.)

Stampa la vitalità di ciascun gladiatore dopo $K$ round del torneo, in ordine dal primo all'ultimo gladiatore della fila.

Input

La prima riga di input contiene due interi separati da spazio $N$ ($2 \le N \le 10^5$) e $K$ ($1 \le K \le 10^{18}$): il numero di gladiatori e il numero di round del torneo.

La riga successiva di input contiene $N$ interi separati da spazio $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): la vitalità iniziale dei gladiatori.

Output

Stampa $N$ interi separati da spazio: la vitalità dei gladiatori al termine del $K$-esimo round del torneo, nell'ordine in cui i gladiatori si trovano attualmente in fila.

Esempi

Input 1

6 3
21 28 24 23 1 12

Output 1

1 1 3 6 3 10

Input 2

3 1000
8 2 10

Output 2

0 0 2