プリモニダス王は、全土で最強の剣闘士を決めるためのトーナメントを開催しようとしています。故郷に名誉と栄光を持ち帰るため、合計 $N$ 人の剣闘士がコロッセオに集まりました。各剣闘士は最初に一定の活力（vitality）を持っています。活力はヒットポイントと似ていて剣闘士が耐えられるダメージ量を表しますが、同時に剣闘士が与えられるダメージ量も表します（強力な一撃にはエネルギーが必要だからです）。

トーナメントは $K$ ラウンドからなります。各ラウンドにおいて、王は残りの活力が少ない順（昇順）に剣闘士を一列に並べます。活力が同じ場合の順序は無作為に決められます。プリモニダス王は、剣闘士の真の強さは打撃に耐える能力にあると信じているため、1 番目の剣闘士（残りの活力が最も少ない剣闘士）に対し、2 番目の剣闘士へ最強の一撃を放つよう命じます。この一撃により、2 番目の剣闘士の活力から 1 番目の剣闘士の活力が引かれます。2 番目の剣闘士はその攻撃を受けた後、（減少した新しい活力を使って）3 番目の剣闘士へ最強の一撃を放ち、以降も同様に続きます。この過程は、最後から 2 番目の剣闘士が最後の剣闘士（誰にも攻撃できない）に最強の一撃を放つまで繰り返されます。

上記の過程において、剣闘士の活力が 0 未満になることは決してないことに注意してください。（活力が 0 の剣闘士は次の剣闘士に微弱な一撃しか放てず、ダメージを一切与えません。）

$K$ ラウンドのトーナメント終了後における各剣闘士の活力を、列の先頭から最後尾までの順に出力してください。

入力

入力の 1 行目には、空白で区切られた 2 つの整数 $N$ ($2 \le N \le 10^5$) と $K$ ($1 \le K \le 10^{18}$) が与えられます。これらはそれぞれ剣闘士の人数とトーナメントのラウンド数を表します。

続く 1 行には、空白で区切られた $N$ 個の整数 $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$) が与えられます。これらは剣闘士の初期活力を表します。

出力

空白で区切られた $N$ 個の整数を出力してください。これらはトーナメントの第 $K$ ラウンド終了時点での各剣闘士の活力であり、その時点で剣闘士が列に並んでいる順序で出力します。

入出力例

入力 1

6 3
21 28 24 23 1 12

出力 1

1 1 3 6 3 10

入力 2

3 1000
8 2 10

出力 2

0 0 2