Vua Primonidas đang tổ chức một giải đấu để tìm ra võ sĩ giác đấu mạnh nhất trên toàn cõi. Tổng cộng có $N$ võ sĩ giác đấu đã tìm đường đến Đấu trường La Mã để mang vinh dự và vinh quang về cho quê hương mình. Mỗi võ sĩ bắt đầu với một lượng sinh lực (vitality) nhất định. Sinh lực tương tự như điểm máu ở chỗ nó phản ánh lượng sát thương mà một võ sĩ có thể chịu đựng, nhưng nó cũng biểu thị lượng sát thương mà họ có thể gây ra (vì cần có năng lượng để tung ra những đòn đánh mạnh).

Giải đấu bao gồm $K$ vòng. Mỗi vòng, nhà vua xếp các võ sĩ thành một hàng theo thứ tự sinh lực còn lại từ ít nhất đến nhiều nhất, nếu bằng nhau thì phân định ngẫu nhiên. Vua Primonidas tin rằng sức mạnh thực sự của một võ sĩ nằm ở khả năng chịu đòn, vì vậy ông ra lệnh cho võ sĩ đầu tiên (người có sinh lực còn lại thấp nhất) tung đòn mạnh nhất của mình vào võ sĩ thứ hai. Đòn này làm giảm sinh lực của võ sĩ thứ hai đi một lượng bằng sinh lực của võ sĩ thứ nhất. Sau khi võ sĩ thứ hai nhận đòn, họ tung đòn mạnh nhất của mình (sử dụng mức sinh lực mới đã bị giảm) vào võ sĩ thứ ba, và cứ tiếp tục như vậy. Quá trình này lặp lại cho đến khi võ sĩ áp chót tung đòn mạnh nhất vào võ sĩ cuối cùng (người không được tấn công ai cả).

Lưu ý rằng trong quá trình trên, sinh lực của một võ sĩ không bao giờ giảm xuống dưới 0. (Một võ sĩ có sinh lực bằng 0 sẽ tung ra một đòn yếu ớt không gây sát thương cho võ sĩ tiếp theo.)

Hãy in ra sinh lực của từng võ sĩ sau $K$ vòng giải đấu, theo thứ tự từ võ sĩ đầu tiên đến võ sĩ cuối cùng trong hàng.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa hai số nguyên cách nhau bởi dấu cách $N$ ($2 \le N \le 10^5$) và $K$ ($1 \le K \le 10^{18}$): số lượng võ sĩ giác đấu và số vòng của giải đấu.

Dòng tiếp theo của dữ liệu vào chứa $N$ số nguyên cách nhau bởi dấu cách $v_1, v_2, \dots, v_N$ ($0 \le v_i \le 10^{18}$): sinh lực ban đầu của các võ sĩ giác đấu.

Dữ liệu ra

In ra $N$ số nguyên cách nhau bởi dấu cách: sinh lực của các võ sĩ giác đấu vào cuối vòng thứ $K$ của giải đấu, theo thứ tự các võ sĩ hiện đang đứng trong hàng.

Ví dụ

Dữ liệu vào 1

6 3
21 28 24 23 1 12

Dữ liệu ra 1

1 1 3 6 3 10

Dữ liệu vào 2

3 1000
8 2 10

Dữ liệu ra 2

0 0 2