Primonidas 國王正喺度舉辦一場錦標賽，想搵出全天下最強嘅角鬥士。總共有 $N$ 位角鬥士嚟到競技場，為自己嘅家鄉爭取榮譽同光彩。每位角鬥士喺一開始都有一定數量嘅體力值（vitality）。體力值類似生命值，既反映咗一位角鬥士可以承受幾多傷害，同時亦代表佢哋可以造成幾多傷害（因為打出重擊係需要消耗體力嘅）。

錦標賽總共有 $K$ 輪。每一輪，國王都會將所有角鬥士按剩餘體力值由細到大排成一行，如果體力值一樣就隨機排。Primonidas 國王深信角鬥士真正嘅實力在於佢哋捱打嘅能力，所以佢命令排第一嘅角鬥士（即係剩餘體力值最低嗰位）向排第二嘅角鬥士使出全力一擊。呢一擊會喺第二位角鬥士嘅體力值入面扣減第一位角鬥士嘅體力值。第二位角鬥士捱咗呢一擊之後，就會（用佢扣減後嘅新體力值）向第三位角鬥士使出全力一擊，如此類推。呢個過程會一直重複，直到尾二嗰位角鬥士向最後一位角鬥士使出全力一擊為止（最後一位角鬥士唔會攻擊任何人）。

請注意，喺上面嘅過程入面，角鬥士嘅體力值永遠唔會跌到低過零。（體力值為零嘅角鬥士對下一位角鬥士打出嘅軟弱一擊唔會造成任何傷害。）

請輸出經過 $K$ 輪錦標賽之後每位角鬥士嘅體力值，按隊列入面由第一位到最後一位角鬥士嘅順序排列。

輸入格式

輸入嘅第一行包含兩個由空格隔開嘅整數 $N$（$2 \le N \le 10^5$）同 $K$（$1 \le K \le 10^{18}$）：分別代表角鬥士嘅人數同埋錦標賽嘅輪數。

輸入嘅下一行包含 $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