Raja Primonidas sedang menyelenggarakan sebuah turnamen untuk menemukan gladiator terkuat di seluruh negeri. Secara keseluruhan, $N$ gladiator telah datang ke Koloseum untuk membawa pulang kehormatan dan kejayaan bagi kampung halaman mereka. Setiap gladiator memulai dengan sejumlah vitalitas tertentu. Vitalitas mirip dengan poin kesehatan karena mencerminkan jumlah kerusakan yang dapat diterima oleh seorang gladiator, tetapi juga merepresentasikan jumlah kerusakan yang dapat mereka berikan (karena energi diperlukan untuk pukulan yang kuat).

Turnamen ini terdiri dari $K$ ronde. Pada setiap ronde, sang raja menyusun para gladiator dalam satu barisan dari vitalitas tersisa paling sedikit hingga paling banyak, dengan memecah seri secara acak. Raja Primonidas percaya bahwa kekuatan sejati seorang gladiator terletak pada kemampuannya menahan pukulan, sehingga ia memerintahkan gladiator pertama (yang memiliki vitalitas tersisa paling rendah) untuk melancarkan pukulan terkuatnya kepada gladiator kedua. Pukulan ini mengurangi vitalitas gladiator kedua sebesar vitalitas gladiator pertama. Setelah gladiator kedua menerima pukulan tersebut, ia melancarkan pukulan terkuatnya (menggunakan vitalitas barunya yang telah berkurang) kepada gladiator ketiga, dan seterusnya. Proses ini berulang hingga gladiator kedua dari terakhir melancarkan pukulan terkuatnya kepada gladiator terakhir (yang tidak mendapat kesempatan untuk menyerang siapa pun).

Perhatikan bahwa dalam proses di atas, vitalitas seorang gladiator tidak pernah bisa turun di bawah nol. (Seorang gladiator dengan vitalitas nol hanya melancarkan pukulan lemah tanpa kerusakan kepada gladiator berikutnya.)

Cetak vitalitas setiap gladiator setelah $K$ ronde turnamen, berurutan dari gladiator pertama hingga gladiator terakhir di dalam barisan.

Masukan

Baris pertama masukan berisi dua bilangan bulat yang dipisahkan spasi $N$ ($2 \le N \le 10^5$) dan $K$ ($1 \le K \le 10^{18}$): jumlah gladiator dan jumlah ronde dalam turnamen.

Baris masukan berikutnya berisi $N$ bilangan bulat yang dipisahkan spasi $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): vitalitas awal para gladiator.

Keluaran

Cetak $N$ bilangan bulat yang dipisahkan spasi: vitalitas para gladiator pada akhir ronde ke-$K$ turnamen, sesuai urutan para gladiator berdiri di dalam barisan saat itu.

Contoh

Masukan 1

6 3
21 28 24 23 1 12

Keluaran 1

1 1 3 6 3 10

Masukan 2

3 1000
8 2 10

Keluaran 2

0 0 2