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