Kuningas Primonidas järjestää turnauksen löytääkseen kaikkien maiden vahvimman gladiaattorin. Yhteensä $N$ gladiaattoria on saapunut Colosseumille tuodakseen kunniaa ja mainetta kotikaupungeilleen. Jokaisella gladiaattorilla on aluksi tietty määrä elinvoimaa (vitality). Elinvoima muistuttaa osumapisteitä siinä, että se kuvaa gladiaattorin kestämän vahingon määrää, mutta se kuvaa myös gladiaattorin tekemän vahingon määrää (sillä voimakkaisiin iskuihin tarvitaan energiaa).

Turnaus koostuu $K$ kierroksesta. Jokaisella kierroksella kuningas järjestää gladiaattorit jonoon pienimmästä jäljellä olevasta elinvoimasta suurimpaan, ratkaisten tasapelit satunnaisesti. Kuningas Primonidas uskoo, että gladiaattorin todellinen vahvuus piilee kyvyssä kestää iskuja, joten hän määrää ensimmäisen gladiaattorin (sen, jolla on vähiten elinvoimaa jäljellä) antamaan voimakkaimman iskunsa toiselle gladiaattorille. Tämä isku vähentää ensimmäisen gladiaattorin elinvoiman toisen gladiaattorin elinvoimasta. Kun toinen gladiaattori on ottanut osuman vastaan, hän antaa voimakkaimman iskunsa (käyttäen uutta, alentunutta elinvoimaansa) kolmannelle gladiaattorille, ja niin edelleen. Tätä toistetaan, kunnes toiseksi viimeinen gladiaattori antaa voimakkaimman iskunsa viimeiselle gladiaattorille (joka ei pääse hyökkäämään kenenkään kimppuun).

Huomaa, että yllä kuvatussa prosessissa gladiaattorin elinvoima ei voi koskaan laskea nollan alapuolelle. (Gladiaattori, jonka elinvoima on nolla, antaa seuraavalle gladiaattorille heikon iskun, joka ei aiheuta lainkaan vahinkoa.)

Tulosta kunkin gladiaattorin elinvoima $K$ turnauskierroksen jälkeen järjestyksessä jonon ensimmäisestä gladiaattorista viimeiseen.

Syöte

Syötteen ensimmäinen rivi sisältää kaksi välilyönnillä erotettua kokonaislukua $N$ ($2 \le N \le 10^5$) ja $K$ ($1 \le K \le 10^{18}$): gladiaattoreiden lukumäärän ja turnauksen kierrosten lukumäärän.

Syötteen seuraava rivi sisältää $N$ välilyönnein erotettua kokonaislukua $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): gladiaattoreiden alkuperäisen elinvoiman.

Tuloste

Tulosta $N$ välilyönnein erotettua kokonaislukua: gladiaattoreiden elinvoimat turnauksen $K$:nnen kierroksen lopussa siinä järjestyksessä, jossa gladiaattorit sillä hetkellä seisovat jonossa.

Esimerkit

Syöte 1

6 3
21 28 24 23 1 12

Tuloste 1

1 1 3 6 3 10

Syöte 2

3 1000
8 2 10

Tuloste 2

0 0 2